Submission #1602678


Source Code Expand

//In the name of god
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second

using namespace std;
typedef long long ll;
#define set set1
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;


int ans[maxn];
int pl[maxn];
int segt[4 * maxn];
int f1[4 * maxn],f2[4 * maxn];
inline int lz1(int v,int s,int e,int val){
	f2[v] = 0;
	segt[v] = (e - s) * val;
	f1[v] = val;
}
inline int lz2(int v,int s,int e,int val){
	f2[v] += val;
	segt[v] += (e - s) * val;
}
inline int shift(int v,int s,int e){
	int lc = 2 * v,rc = 2 * v + 1,m = (e + s) / 2;
	if (f1[v] != 0){
		lz1(lc,s,m,f1[v]);
		lz1(rc,m,e,f1[v]);
		f1[v] = 0;
	}
	if (f2[v] != 0){
		lz2(lc,s,m,f2[v]);
		lz2(rc,m,e,f2[v]);
		f2[v] = 0;
	}
	return 0;
}
int set(int v,int l,int r,int s,int e,int val){
	if ( r<= l) return 0;
	if (s >= r || e <= l) return 0;
	if (s >= l && e <= r){
		lz1(v,s,e,val);
		return 0;
	}
	shift(v,s,e);
	int m = (e + s) / 2;
	set(2 * v,l,r,s,m,val);
	set(2 * v + 1,l,r,m,e,val);
	return 0;
}
int update(int v,int l,int r,int s,int e,int val){
	if (r <= l) return 0;
	if (s >= r || e <= l) return 0;
	if (s >= l && e <= r){
		lz2(v,s,e,val);
		return 0;
	}
	shift(v,s,e);
	int m = (e + s) / 2;
	update(2 * v,l,r,s,m,val);
	update(2 * v + 1,l,r,m,e,val);
	return 0;
}
int query(int v,int ind,int s,int e){
	if (ind < s || ind >= e) return 0;
	if (e - s == 1){
		return segt[v];
	}
	shift(v,s,e);
	int m = (e + s) / 2;
	return query(2 * v,ind,s,m) + query(2 * v + 1,ind,m,e);
}
int build(int v,int s,int e){
	f1[v] = f2[v] = -1;
	if (e - s == 1) return 0;
	int m = (e + s) / 2;
	build(2 * v,s,m);
	build(2 * v + 1,m,e);
}
int q,x;
int bs(int lo,int hi,int t,int v){
	int m,found = (t == 0) ?lo - 1:hi + 1;
	while(lo <= hi){
		m = (lo + hi) / 2;
		int as = query(1,m,0,q);
//		cout << m << ' ' << as << endl;
		if (t){
			as = x - as;
			if (as<=v){
				found = m;
				hi = m - 1;
			}else lo = m + 1;
		}else{
			if (as <= v){
				found = m;
				lo = m + 1;
			}else hi = m - 1;
		}
	}
	return found;
}
int main(){
	ios_base::sync_with_stdio(0) , cin.tie(0);
	int k;
	cin >> x >> k;
	int r;
	vector<int> swp;
	swp.pb(1e9 + 1);
	for (int i = 0;i < k;i++){
		cin >> r;
		swp.pb(r);
	}
	sort(swp.begin(),swp.end());
	cin >> q;
	int t,a,sz = q - 1;
	vector<pii> qs;
	vector<pii> ts;
	for (int i = 0;i < q;i++){
		cin >> t >>  a;
		qs.pb({a,i});
		ts.pb({-t,i});
	}
	sort(qs.begin(),qs.end());
	sort(ts.begin(),ts.end());
	build(1,0,q);
	for (int i = 0;i < q;i++){
		pl[qs[i].S] = i;
		set(1,i,i + 1,0,q,qs[i].F);
	}
	for (int i= 0;i < q;i++){
		cout << i << ' '  << query(1,i,0,q) << endl;
	}
	int sw = 0,ca;
	int lt = 0;
	for (int i = 0;i <swp.size();i++){
		while(sz >= 0 && -ts[sz].F <= swp[i]){
			ca = query(1,pl[ts[sz].S],0,q);
		//	cout << ca<< endl;
			int t = -ts[sz].F;
			if (i % 2){
				ca = min(x,ca + (t - lt));
			}else {
				ca = max(0,ca - (t - lt));
			}
		//	cout << ca << endl;
			ans[ts[sz].S] = ca;
		//	cout << sz << endl;
		//	cout << ts[sz].S <<  ' ' << ca << endl;
			sz--;

			ts.pop_back();
		}
		int in = bs(0,q - 1,i % 2,swp[i] - lt);
//	cout<< in << endl;
		if (i % 2){
			set(1,in,q,0,q,x);
			update(1,0,in,0,q,swp[i] - lt);
		}else {
			set(1,0,in + 1,0,q,0);
			update(1,in + 1,q,0,q,-(swp[i] - lt));
		}
		//cout << i << endl;
		lt = swp[i];
	}
	for (int i= 0;i < q;i++){
		cout << ans[i] << '\n';
	}
	return 0;
}

Submission Info

Submission Time
Task F - Sandglass
User chaxy_2000
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3517 Byte
Status WA
Exec Time 453 ms
Memory 9972 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
WA × 3
WA × 42
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt
Case Name Status Exec Time Memory
0_000.txt WA 1 ms 2304 KB
0_001.txt WA 1 ms 2304 KB
0_002.txt WA 1 ms 2304 KB
1_003.txt WA 438 ms 8436 KB
1_004.txt WA 438 ms 8436 KB
1_005.txt WA 449 ms 8436 KB
1_006.txt WA 430 ms 8436 KB
1_007.txt WA 445 ms 8564 KB
1_008.txt WA 444 ms 8564 KB
1_009.txt WA 423 ms 8564 KB
1_010.txt WA 442 ms 8692 KB
1_011.txt WA 450 ms 8564 KB
1_012.txt WA 428 ms 8820 KB
1_013.txt WA 438 ms 8820 KB
1_014.txt WA 449 ms 8820 KB
1_015.txt WA 426 ms 8948 KB
1_016.txt WA 435 ms 9076 KB
1_017.txt WA 453 ms 8948 KB
1_018.txt WA 432 ms 9204 KB
1_019.txt WA 437 ms 9204 KB
1_020.txt WA 444 ms 9204 KB
1_021.txt WA 427 ms 9204 KB
1_022.txt WA 439 ms 9460 KB
1_023.txt WA 444 ms 9332 KB
1_024.txt WA 430 ms 9332 KB
1_025.txt WA 437 ms 9588 KB
1_026.txt WA 441 ms 9588 KB
1_027.txt WA 426 ms 9460 KB
1_028.txt WA 433 ms 9460 KB
1_029.txt WA 440 ms 9844 KB
1_030.txt WA 428 ms 9588 KB
1_031.txt WA 434 ms 9588 KB
1_032.txt WA 447 ms 9972 KB
1_033.txt WA 244 ms 8684 KB
1_034.txt WA 249 ms 8512 KB
1_035.txt WA 441 ms 9588 KB
1_036.txt WA 239 ms 8812 KB
1_037.txt WA 250 ms 8640 KB
1_038.txt WA 443 ms 9844 KB
1_039.txt WA 241 ms 8556 KB
1_040.txt WA 253 ms 8896 KB
1_041.txt WA 445 ms 9972 KB