ABC 221 D - Online games (思维+离散化)

链接

题意：

给出你n个人工作的区间，第一个是开始时间，第二个是工作多长时间，问有多少时间有多少人在工作。

分析：

首先我们如果不看数据范围的话我们肯定想用差分来做，但是现在区间是$1e9$所以我们不能直接用差分，看是我们知道一共n个人那么最多有2n个节点，我们把这些节点提取出来不就是另一种差分的方式吗？

把2n个点离散化，然后我们知道差分的话要有两个端点，左端点是开始时间，右端点应该是结束时间+1，因为正常差分[l,r]，我们是在a[l]++,a[r+1]–;所以我们的右端点应该是结束时间+1，注意数组要开$4e5$的.

// Problem: B. Diameter of Graph
// Contest: Codeforces - Codeforces Round #745 (Div. 2)
// URL: https://codeforces.com/contest/1581/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 4e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};void init()
{}
ll n;
ll sum[maxn];
struct node
{ll x, y;ll a, b;
} q[maxn];
bool cmp(node a, node b)
{if(a.y != b.y)return a.y < b.y;return a.x < b.x;
}
ll a[maxn], cnt, b[maxn];
map<ll, ll> mp;
void solve()
{cin >> n;for(int i = 1; i <= n; i++){cin >> q[i].x >> q[i].y;q[i].y += q[i].x;if(!mp[q[i].x])         {a[++cnt] = q[i].x, mp[q[i].x] = 1;}if(!mp[q[i].y]) {a[++cnt] = q[i].y, mp[q[i].y] = 1;}}sort(a + 1, a + 1 + cnt);for(int i = 1; i <= cnt; i++) mp[a[i]] = i;//cout << a[i] << " ";//puts("");for(int i = 1; i <= n; i++){b[mp[q[i].x]]++;b[mp[q[i].y]]--;}ll top = 0;for(int i = 1; i <= cnt; i++){//cout<if(b[i] == 0){b[i]+=b[i-1];continue;}else{sum[b[i - 1]] += a[i] - top;b[i] += b[i - 1];top = a[i];///cout << b[i] << " ****" << endl;}}for(int i = 1; i <= n; i++){cout << sum[i] << " ";}}int main()
{init();ll t = 1;///scanf("%lld",&t);while(t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！