# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1014202 |
2024-07-04T13:58:31 Z |
pcc |
New Home (APIO18_new_home) |
C++17 |
|
5000 ms |
524476 KB |
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define _all(T) T.begin(),T.end()
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e6;
const int inf = 1e9;
const int lim = 1e8+10;
struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
int seg[mxn*4];
pii op[mxn*15];
int head[mxn];
int cnt = 0;
SEG(){
fill(seg,seg+mxn*4,-inf);
}
void modify(int now,int l,int r,int s,int e,int v,bool rec = false){
if(rec&&now == 0){
cnt++;
head[cnt] = head[cnt-1];
}
if(l>=s&&e>=r){
if(rec){
op[++head[cnt]] = pii(now,seg[now]);
}
seg[now] = max(seg[now],v);
return;
}
if(mid>=s)modify(ls,l,mid,s,e,v,rec);
if(mid<e)modify(rs,mid+1,r,s,e,v,rec);
return;
}
void undo(){
assert(cnt);
while(head[cnt]>head[cnt-1]){
auto &[p,v] = op[head[cnt]--];
seg[p] = v;
}
cnt--;
return;
}
int getval(int now,int l,int r,int p){
if(l == r)return seg[now];
if(mid>=p)return max(seg[now],getval(ls,l,mid,p));
else return max(seg[now],getval(rs,mid+1,r,p));
}
#undef mid
#undef ls
#undef rs
};
SEG seg1,seg2;
int N,K,Q;
multiset<int> st[mxn];
vector<int> all;
vector<int> allt;
vector<pii> req;
array<int,4> shop[mxn];
int ans[mxn];
vector<pii> tseg[mxn*4];
vector<pii> ask[mxn];
void addev(int now,int l,int r,int s,int e,pii val){
assert(e>=s);
if(l>=s&&e>=r){
tseg[now].push_back(val);
return;
}
int mid = (l+r)>>1;
if(mid>=s)addev(now*2+1,l,mid,s,e,val);
if(mid<e)addev(now*2+2,mid+1,r,s,e,val);
return;
}
void del(int pos,int tp){
st[tp].erase(st[tp].find(pos));
auto lit = --st[tp].lower_bound(pos);
auto rit = st[tp].lower_bound(pos);
int mid = all[*lit]+(all[*rit]-all[*lit])/2;
int mp = upper_bound(_all(all),mid)-all.begin();
//cerr<<"DEL: "<<pos<<' '<<tp<<"::"<<*lit<<' '<<mp<<' '<<*rit<<endl;
seg1.modify(0,0,all.size(),*lit,mp-1,-all[*lit],1);
seg2.modify(0,0,all.size(),mp,*rit,all[*rit],1);
//cerr<<"DEL DONE! "<<endl;
return;
}
void undo(){
seg1.undo();
seg2.undo();
}
void dfs(int now,int l,int r){
//cerr<<"DFS IN: "<<l<<' '<<r<<endl;
for(auto &i:tseg[now])del(i.fs,i.sc);
if(l == r){
for(auto &i:ask[l]){//p,idx
//cerr<<"ASK: "<<i.fs<<','<<i.sc<<' '<<all[i.fs]<<' '<<seg1.getval(0,0,all.size(),i.fs)<<' '<<seg2.getval(0,0,all.size(),i.fs)<<endl;
ans[i.sc] = max(all[i.fs]+seg1.getval(0,0,all.size(),i.fs),seg2.getval(0,0,all.size(),i.fs)-all[i.fs]);
}
}
else{
int mid = (l+r)>>1;
dfs(now*2+1,l,mid);
dfs(now*2+2,mid+1,r);
}
for(auto &[pos,tp]:tseg[now]){
undo();
//cerr<<"UNDO: "<<pos<<','<<tp<<endl;
st[tp].insert(pos);
}
//cerr<<"DFS OUT: "<<l<<' '<<r<<endl;
return;
}
int main(){
cin>>N>>K>>Q;
allt.push_back(-1);
for(int i = 1;i<=N;i++){
cin>>shop[i][0]>>shop[i][1]>>shop[i][2]>>shop[i][3];//x,t,a,b
all.push_back(shop[i][0]);
allt.push_back(shop[i][2]);
allt.push_back(shop[i][3]);
}
for(int i = 0;i<Q;i++){
int l,y;
cin>>l>>y;
all.push_back(l);
allt.push_back(y);
req.push_back(pii(l,y));
}
all.push_back(-inf);all.push_back(inf);
sort(_all(all));all.resize(unique(_all(all))-all.begin());
sort(_all(allt));allt.resize(unique(_all(allt))-allt.begin());
//cerr<<"ALL: ";for(auto &i:all)cerr<<i<<' ';cerr<<endl;
//cerr<<"ALLT: ";for(auto &i:allt)cerr<<i<<' ';cerr<<endl;
for(int i = 1;i<=K;i++){
st[i].insert(0);
st[i].insert(all.size()-1);
}
for(int i = 1;i<=N;i++){
shop[i][0] = lower_bound(_all(all),shop[i][0])-all.begin();
st[shop[i][1]].insert(shop[i][0]);
shop[i][2] = lower_bound(_all(allt),shop[i][2])-allt.begin();
shop[i][3] = lower_bound(_all(allt),shop[i][3])-allt.begin();
}
for(int i = 1;i<=K;i++){
for(auto it = ++st[i].begin();it != st[i].end();it++){
int l = *prev(it),r = *it;
int mid = all[l]+(all[r]-all[l])/2;
auto pos = upper_bound(_all(all),mid)-all.begin();
seg1.modify(0,0,all.size(),l,pos-1,-all[l]);
seg2.modify(0,0,all.size(),pos,r,all[r]);
}
}
//cerr<<"INIT DONE!"<<endl;
for(int i = 1;i<=N;i++){
int pos = shop[i][0],tp = shop[i][1],s = shop[i][2],e = shop[i][3];
//cerr<<"ADDEV: "<<0<<' '<<s-1<<' '<<pos<<' '<<tp<<endl;
//cerr<<"ADDEV: "<<e+1<<' '<<allt.size()<<' '<<pos<<' '<<tp<<endl;
addev(0,0,allt.size(),0,s-1,pii(pos,tp));
addev(0,0,allt.size(),e+1,allt.size(),pii(pos,tp));
}
for(int i = 0;i<Q;i++){
auto &[p,t] = req[i];
p = lower_bound(_all(all),p)-all.begin();
t = lower_bound(_all(allt),t)-allt.begin();
//cerr<<"ASK POS: "<<p<<' '<<t<<endl;
ask[t].push_back(pii(p,i));
}
//cerr<<"ADDEV DONE!"<<' '<<seg1.getval(0,0,all.size(),req[0].fs)<<' '<<seg2.getval(0,0,all.size(),req[0].fs)<<endl;
dfs(0,0,allt.size());
assert(!seg1.cnt);
assert(!seg2.cnt);
//cerr<<"DFS DONE! "<<endl;
for(int i = 0;i<Q;i++)cout<<(ans[i]>lim?-1:ans[i])<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
430932 KB |
Output is correct |
2 |
Correct |
174 ms |
430932 KB |
Output is correct |
3 |
Correct |
177 ms |
430812 KB |
Output is correct |
4 |
Correct |
175 ms |
430928 KB |
Output is correct |
5 |
Correct |
193 ms |
430932 KB |
Output is correct |
6 |
Correct |
179 ms |
430928 KB |
Output is correct |
7 |
Correct |
188 ms |
430928 KB |
Output is correct |
8 |
Correct |
187 ms |
431072 KB |
Output is correct |
9 |
Correct |
173 ms |
431048 KB |
Output is correct |
10 |
Correct |
176 ms |
430928 KB |
Output is correct |
11 |
Correct |
171 ms |
430932 KB |
Output is correct |
12 |
Correct |
180 ms |
430932 KB |
Output is correct |
13 |
Correct |
174 ms |
430996 KB |
Output is correct |
14 |
Correct |
192 ms |
430932 KB |
Output is correct |
15 |
Correct |
189 ms |
430980 KB |
Output is correct |
16 |
Correct |
184 ms |
430932 KB |
Output is correct |
17 |
Correct |
180 ms |
430932 KB |
Output is correct |
18 |
Correct |
227 ms |
430928 KB |
Output is correct |
19 |
Correct |
178 ms |
431088 KB |
Output is correct |
20 |
Correct |
189 ms |
430928 KB |
Output is correct |
21 |
Correct |
195 ms |
430928 KB |
Output is correct |
22 |
Correct |
175 ms |
430964 KB |
Output is correct |
23 |
Correct |
176 ms |
430928 KB |
Output is correct |
24 |
Correct |
193 ms |
431048 KB |
Output is correct |
25 |
Correct |
190 ms |
430928 KB |
Output is correct |
26 |
Correct |
181 ms |
430932 KB |
Output is correct |
27 |
Correct |
183 ms |
430928 KB |
Output is correct |
28 |
Correct |
175 ms |
430868 KB |
Output is correct |
29 |
Correct |
173 ms |
430932 KB |
Output is correct |
30 |
Correct |
185 ms |
430932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
430932 KB |
Output is correct |
2 |
Correct |
174 ms |
430932 KB |
Output is correct |
3 |
Correct |
177 ms |
430812 KB |
Output is correct |
4 |
Correct |
175 ms |
430928 KB |
Output is correct |
5 |
Correct |
193 ms |
430932 KB |
Output is correct |
6 |
Correct |
179 ms |
430928 KB |
Output is correct |
7 |
Correct |
188 ms |
430928 KB |
Output is correct |
8 |
Correct |
187 ms |
431072 KB |
Output is correct |
9 |
Correct |
173 ms |
431048 KB |
Output is correct |
10 |
Correct |
176 ms |
430928 KB |
Output is correct |
11 |
Correct |
171 ms |
430932 KB |
Output is correct |
12 |
Correct |
180 ms |
430932 KB |
Output is correct |
13 |
Correct |
174 ms |
430996 KB |
Output is correct |
14 |
Correct |
192 ms |
430932 KB |
Output is correct |
15 |
Correct |
189 ms |
430980 KB |
Output is correct |
16 |
Correct |
184 ms |
430932 KB |
Output is correct |
17 |
Correct |
180 ms |
430932 KB |
Output is correct |
18 |
Correct |
227 ms |
430928 KB |
Output is correct |
19 |
Correct |
178 ms |
431088 KB |
Output is correct |
20 |
Correct |
189 ms |
430928 KB |
Output is correct |
21 |
Correct |
195 ms |
430928 KB |
Output is correct |
22 |
Correct |
175 ms |
430964 KB |
Output is correct |
23 |
Correct |
176 ms |
430928 KB |
Output is correct |
24 |
Correct |
193 ms |
431048 KB |
Output is correct |
25 |
Correct |
190 ms |
430928 KB |
Output is correct |
26 |
Correct |
181 ms |
430932 KB |
Output is correct |
27 |
Correct |
183 ms |
430928 KB |
Output is correct |
28 |
Correct |
175 ms |
430868 KB |
Output is correct |
29 |
Correct |
173 ms |
430932 KB |
Output is correct |
30 |
Correct |
185 ms |
430932 KB |
Output is correct |
31 |
Correct |
1232 ms |
453084 KB |
Output is correct |
32 |
Correct |
308 ms |
440264 KB |
Output is correct |
33 |
Correct |
1215 ms |
455184 KB |
Output is correct |
34 |
Correct |
1171 ms |
455080 KB |
Output is correct |
35 |
Correct |
1220 ms |
452988 KB |
Output is correct |
36 |
Correct |
1158 ms |
452988 KB |
Output is correct |
37 |
Correct |
1041 ms |
455364 KB |
Output is correct |
38 |
Correct |
1095 ms |
455108 KB |
Output is correct |
39 |
Correct |
882 ms |
455112 KB |
Output is correct |
40 |
Correct |
889 ms |
455068 KB |
Output is correct |
41 |
Correct |
934 ms |
454848 KB |
Output is correct |
42 |
Correct |
967 ms |
454596 KB |
Output is correct |
43 |
Correct |
260 ms |
441092 KB |
Output is correct |
44 |
Correct |
1014 ms |
455112 KB |
Output is correct |
45 |
Correct |
1079 ms |
454848 KB |
Output is correct |
46 |
Correct |
1108 ms |
454692 KB |
Output is correct |
47 |
Correct |
709 ms |
453300 KB |
Output is correct |
48 |
Correct |
733 ms |
453316 KB |
Output is correct |
49 |
Correct |
760 ms |
453824 KB |
Output is correct |
50 |
Correct |
814 ms |
454596 KB |
Output is correct |
51 |
Correct |
808 ms |
453576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1768 ms |
491360 KB |
Output is correct |
2 |
Correct |
1854 ms |
484080 KB |
Output is correct |
3 |
Correct |
1713 ms |
506704 KB |
Output is correct |
4 |
Correct |
1813 ms |
500304 KB |
Output is correct |
5 |
Correct |
1955 ms |
488884 KB |
Output is correct |
6 |
Correct |
1985 ms |
489296 KB |
Output is correct |
7 |
Correct |
1359 ms |
520016 KB |
Output is correct |
8 |
Correct |
1537 ms |
501056 KB |
Output is correct |
9 |
Correct |
1622 ms |
494432 KB |
Output is correct |
10 |
Correct |
1674 ms |
490288 KB |
Output is correct |
11 |
Correct |
1248 ms |
488976 KB |
Output is correct |
12 |
Correct |
1398 ms |
490212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4698 ms |
524476 KB |
Output is correct |
2 |
Correct |
839 ms |
476208 KB |
Output is correct |
3 |
Execution timed out |
5039 ms |
522368 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
430932 KB |
Output is correct |
2 |
Correct |
174 ms |
430932 KB |
Output is correct |
3 |
Correct |
177 ms |
430812 KB |
Output is correct |
4 |
Correct |
175 ms |
430928 KB |
Output is correct |
5 |
Correct |
193 ms |
430932 KB |
Output is correct |
6 |
Correct |
179 ms |
430928 KB |
Output is correct |
7 |
Correct |
188 ms |
430928 KB |
Output is correct |
8 |
Correct |
187 ms |
431072 KB |
Output is correct |
9 |
Correct |
173 ms |
431048 KB |
Output is correct |
10 |
Correct |
176 ms |
430928 KB |
Output is correct |
11 |
Correct |
171 ms |
430932 KB |
Output is correct |
12 |
Correct |
180 ms |
430932 KB |
Output is correct |
13 |
Correct |
174 ms |
430996 KB |
Output is correct |
14 |
Correct |
192 ms |
430932 KB |
Output is correct |
15 |
Correct |
189 ms |
430980 KB |
Output is correct |
16 |
Correct |
184 ms |
430932 KB |
Output is correct |
17 |
Correct |
180 ms |
430932 KB |
Output is correct |
18 |
Correct |
227 ms |
430928 KB |
Output is correct |
19 |
Correct |
178 ms |
431088 KB |
Output is correct |
20 |
Correct |
189 ms |
430928 KB |
Output is correct |
21 |
Correct |
195 ms |
430928 KB |
Output is correct |
22 |
Correct |
175 ms |
430964 KB |
Output is correct |
23 |
Correct |
176 ms |
430928 KB |
Output is correct |
24 |
Correct |
193 ms |
431048 KB |
Output is correct |
25 |
Correct |
190 ms |
430928 KB |
Output is correct |
26 |
Correct |
181 ms |
430932 KB |
Output is correct |
27 |
Correct |
183 ms |
430928 KB |
Output is correct |
28 |
Correct |
175 ms |
430868 KB |
Output is correct |
29 |
Correct |
173 ms |
430932 KB |
Output is correct |
30 |
Correct |
185 ms |
430932 KB |
Output is correct |
31 |
Correct |
1232 ms |
453084 KB |
Output is correct |
32 |
Correct |
308 ms |
440264 KB |
Output is correct |
33 |
Correct |
1215 ms |
455184 KB |
Output is correct |
34 |
Correct |
1171 ms |
455080 KB |
Output is correct |
35 |
Correct |
1220 ms |
452988 KB |
Output is correct |
36 |
Correct |
1158 ms |
452988 KB |
Output is correct |
37 |
Correct |
1041 ms |
455364 KB |
Output is correct |
38 |
Correct |
1095 ms |
455108 KB |
Output is correct |
39 |
Correct |
882 ms |
455112 KB |
Output is correct |
40 |
Correct |
889 ms |
455068 KB |
Output is correct |
41 |
Correct |
934 ms |
454848 KB |
Output is correct |
42 |
Correct |
967 ms |
454596 KB |
Output is correct |
43 |
Correct |
260 ms |
441092 KB |
Output is correct |
44 |
Correct |
1014 ms |
455112 KB |
Output is correct |
45 |
Correct |
1079 ms |
454848 KB |
Output is correct |
46 |
Correct |
1108 ms |
454692 KB |
Output is correct |
47 |
Correct |
709 ms |
453300 KB |
Output is correct |
48 |
Correct |
733 ms |
453316 KB |
Output is correct |
49 |
Correct |
760 ms |
453824 KB |
Output is correct |
50 |
Correct |
814 ms |
454596 KB |
Output is correct |
51 |
Correct |
808 ms |
453576 KB |
Output is correct |
52 |
Correct |
788 ms |
458236 KB |
Output is correct |
53 |
Correct |
809 ms |
460088 KB |
Output is correct |
54 |
Correct |
855 ms |
454280 KB |
Output is correct |
55 |
Correct |
836 ms |
456156 KB |
Output is correct |
56 |
Correct |
803 ms |
457000 KB |
Output is correct |
57 |
Correct |
931 ms |
454956 KB |
Output is correct |
58 |
Correct |
882 ms |
455968 KB |
Output is correct |
59 |
Correct |
847 ms |
456644 KB |
Output is correct |
60 |
Correct |
914 ms |
455360 KB |
Output is correct |
61 |
Correct |
274 ms |
447080 KB |
Output is correct |
62 |
Correct |
704 ms |
459880 KB |
Output is correct |
63 |
Correct |
767 ms |
455972 KB |
Output is correct |
64 |
Correct |
790 ms |
455616 KB |
Output is correct |
65 |
Correct |
902 ms |
455100 KB |
Output is correct |
66 |
Correct |
941 ms |
454592 KB |
Output is correct |
67 |
Correct |
315 ms |
442816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
430932 KB |
Output is correct |
2 |
Correct |
174 ms |
430932 KB |
Output is correct |
3 |
Correct |
177 ms |
430812 KB |
Output is correct |
4 |
Correct |
175 ms |
430928 KB |
Output is correct |
5 |
Correct |
193 ms |
430932 KB |
Output is correct |
6 |
Correct |
179 ms |
430928 KB |
Output is correct |
7 |
Correct |
188 ms |
430928 KB |
Output is correct |
8 |
Correct |
187 ms |
431072 KB |
Output is correct |
9 |
Correct |
173 ms |
431048 KB |
Output is correct |
10 |
Correct |
176 ms |
430928 KB |
Output is correct |
11 |
Correct |
171 ms |
430932 KB |
Output is correct |
12 |
Correct |
180 ms |
430932 KB |
Output is correct |
13 |
Correct |
174 ms |
430996 KB |
Output is correct |
14 |
Correct |
192 ms |
430932 KB |
Output is correct |
15 |
Correct |
189 ms |
430980 KB |
Output is correct |
16 |
Correct |
184 ms |
430932 KB |
Output is correct |
17 |
Correct |
180 ms |
430932 KB |
Output is correct |
18 |
Correct |
227 ms |
430928 KB |
Output is correct |
19 |
Correct |
178 ms |
431088 KB |
Output is correct |
20 |
Correct |
189 ms |
430928 KB |
Output is correct |
21 |
Correct |
195 ms |
430928 KB |
Output is correct |
22 |
Correct |
175 ms |
430964 KB |
Output is correct |
23 |
Correct |
176 ms |
430928 KB |
Output is correct |
24 |
Correct |
193 ms |
431048 KB |
Output is correct |
25 |
Correct |
190 ms |
430928 KB |
Output is correct |
26 |
Correct |
181 ms |
430932 KB |
Output is correct |
27 |
Correct |
183 ms |
430928 KB |
Output is correct |
28 |
Correct |
175 ms |
430868 KB |
Output is correct |
29 |
Correct |
173 ms |
430932 KB |
Output is correct |
30 |
Correct |
185 ms |
430932 KB |
Output is correct |
31 |
Correct |
1232 ms |
453084 KB |
Output is correct |
32 |
Correct |
308 ms |
440264 KB |
Output is correct |
33 |
Correct |
1215 ms |
455184 KB |
Output is correct |
34 |
Correct |
1171 ms |
455080 KB |
Output is correct |
35 |
Correct |
1220 ms |
452988 KB |
Output is correct |
36 |
Correct |
1158 ms |
452988 KB |
Output is correct |
37 |
Correct |
1041 ms |
455364 KB |
Output is correct |
38 |
Correct |
1095 ms |
455108 KB |
Output is correct |
39 |
Correct |
882 ms |
455112 KB |
Output is correct |
40 |
Correct |
889 ms |
455068 KB |
Output is correct |
41 |
Correct |
934 ms |
454848 KB |
Output is correct |
42 |
Correct |
967 ms |
454596 KB |
Output is correct |
43 |
Correct |
260 ms |
441092 KB |
Output is correct |
44 |
Correct |
1014 ms |
455112 KB |
Output is correct |
45 |
Correct |
1079 ms |
454848 KB |
Output is correct |
46 |
Correct |
1108 ms |
454692 KB |
Output is correct |
47 |
Correct |
709 ms |
453300 KB |
Output is correct |
48 |
Correct |
733 ms |
453316 KB |
Output is correct |
49 |
Correct |
760 ms |
453824 KB |
Output is correct |
50 |
Correct |
814 ms |
454596 KB |
Output is correct |
51 |
Correct |
808 ms |
453576 KB |
Output is correct |
52 |
Correct |
1768 ms |
491360 KB |
Output is correct |
53 |
Correct |
1854 ms |
484080 KB |
Output is correct |
54 |
Correct |
1713 ms |
506704 KB |
Output is correct |
55 |
Correct |
1813 ms |
500304 KB |
Output is correct |
56 |
Correct |
1955 ms |
488884 KB |
Output is correct |
57 |
Correct |
1985 ms |
489296 KB |
Output is correct |
58 |
Correct |
1359 ms |
520016 KB |
Output is correct |
59 |
Correct |
1537 ms |
501056 KB |
Output is correct |
60 |
Correct |
1622 ms |
494432 KB |
Output is correct |
61 |
Correct |
1674 ms |
490288 KB |
Output is correct |
62 |
Correct |
1248 ms |
488976 KB |
Output is correct |
63 |
Correct |
1398 ms |
490212 KB |
Output is correct |
64 |
Correct |
4698 ms |
524476 KB |
Output is correct |
65 |
Correct |
839 ms |
476208 KB |
Output is correct |
66 |
Execution timed out |
5039 ms |
522368 KB |
Time limit exceeded |
67 |
Halted |
0 ms |
0 KB |
- |