Submission #1602710
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
#define int ll
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];
bool has[4 * maxn];
inline int lz1(int v,int s,int e,int val){
f2[v] = 0;
has[v] = true;
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 (has[v] != false){
lz1(lc,s,m,f1[v]);
lz1(rc,m,e,f1[v]);
f1[v] = 0;
has[v] = false;
}
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);
segt[v] = segt[2 * v] + segt[2 * v + 1];
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);
segt[v] = segt[2 * v] + segt[2 * v + 1];
return 0;
}
int query(int v,int ind,int s,int e){
if (ind < s || ind >= e) return 0;
// cout << v << ' ' << s << ' ' << e << ' ' << segt[v] << endl;
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] = 0;
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);
if (t){
if (as + v > x){
found = m;
hi = m - 1;
}else lo = m + 1;
}else{
if (as < v){
found = m;
lo = m + 1;
}else hi = m - 1;
}
}
return found;
}
int32_t 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);
}
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);
int t = -ts[sz].F;
if (i % 2){
ca = min(x,ca + (t - lt));
}else {
ca = max(0ll,ca - (t - lt));
}
ans[ts[sz].S] = ca;
sz--;
ts.pop_back();
}
int in = bs(0,q - 1,i % 2,swp[i] - lt);
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 << in << endl;
// for (int i= 0;i < q;i++){
// cout << i << ' ' << query(1,i,0,q) << endl;
/// }
// cout << endl << endl << 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 |
700 |
Code Size |
3608 Byte |
Status |
AC |
Exec Time |
372 ms |
Memory |
17300 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
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 |
AC |
2 ms |
6400 KB |
0_001.txt |
AC |
2 ms |
6400 KB |
0_002.txt |
AC |
2 ms |
6400 KB |
1_003.txt |
AC |
321 ms |
15636 KB |
1_004.txt |
AC |
347 ms |
15636 KB |
1_005.txt |
AC |
355 ms |
15636 KB |
1_006.txt |
AC |
282 ms |
15764 KB |
1_007.txt |
AC |
349 ms |
15764 KB |
1_008.txt |
AC |
363 ms |
15764 KB |
1_009.txt |
AC |
273 ms |
15764 KB |
1_010.txt |
AC |
330 ms |
17300 KB |
1_011.txt |
AC |
372 ms |
15764 KB |
1_012.txt |
AC |
272 ms |
15892 KB |
1_013.txt |
AC |
314 ms |
15892 KB |
1_014.txt |
AC |
358 ms |
15892 KB |
1_015.txt |
AC |
274 ms |
15892 KB |
1_016.txt |
AC |
289 ms |
16020 KB |
1_017.txt |
AC |
337 ms |
15892 KB |
1_018.txt |
AC |
272 ms |
16020 KB |
1_019.txt |
AC |
280 ms |
16020 KB |
1_020.txt |
AC |
305 ms |
16020 KB |
1_021.txt |
AC |
267 ms |
16020 KB |
1_022.txt |
AC |
278 ms |
16148 KB |
1_023.txt |
AC |
291 ms |
16148 KB |
1_024.txt |
AC |
269 ms |
15892 KB |
1_025.txt |
AC |
287 ms |
16276 KB |
1_026.txt |
AC |
282 ms |
16276 KB |
1_027.txt |
AC |
268 ms |
16020 KB |
1_028.txt |
AC |
275 ms |
16020 KB |
1_029.txt |
AC |
283 ms |
16276 KB |
1_030.txt |
AC |
269 ms |
16020 KB |
1_031.txt |
AC |
277 ms |
16020 KB |
1_032.txt |
AC |
283 ms |
16404 KB |
1_033.txt |
AC |
75 ms |
15588 KB |
1_034.txt |
AC |
80 ms |
15588 KB |
1_035.txt |
AC |
281 ms |
16276 KB |
1_036.txt |
AC |
77 ms |
15716 KB |
1_037.txt |
AC |
81 ms |
15716 KB |
1_038.txt |
AC |
285 ms |
16276 KB |
1_039.txt |
AC |
76 ms |
15460 KB |
1_040.txt |
AC |
87 ms |
15716 KB |
1_041.txt |
AC |
286 ms |
16404 KB |