oj.uz

Submission #924633

# Submission time Handle Problem Language Result Execution time Memory
924633 2024-02-09T10:35:22 Z winter0101 New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 391348 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=3e5+9;
const int mx=2e8;
const int mn=-1e8;
set<int>cord[maxn];
multiset<int>dubi[maxn];
int n,k,q,line;
int now=0;
struct lne{
int l,r,tim;
bool operator < (const lne &p)const {
if (l==p.l&&r==p.r)return tim<p.tim;
if (l==p.l)return r<p.r;
return l<p.l;
}
};
multiset<lne>temp[maxn];
vector<pii>st[maxn*3*4];
void update(int id,int l,int r,int u,int v,const pii &x){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id].pb(x);
return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,x);
update(id<<1|1,mid+1,r,u,v,x);
}
void add_line(int l,int r,int type,int tme){
temp[type].insert({l,r,tme});
}
void del_line(int l,int r,int type,int del){
auto it=temp[type].lower_bound({l,r,0});
auto tmp=(*it);
update(1,1,line,tmp.tim,del-1,{tmp.l,tmp.r});
temp[type].erase(it);
}
void add_point(int x,int type,int tme){
if (cord[type].empty())now++;
if (cord[type].find(x)!=cord[type].end()){
dubi[type].insert(x);
return;
}
if (cord[type].empty()){
cord[type].insert(x);
add_line(mn,x,type,tme);
add_line(x,mx,type,tme);
return;
}
auto it=cord[type].upper_bound(x);
if (it==cord[type].end()){
it--;
del_line((*it),mx,type,tme);
add_line(x,mx,type,tme);
add_line((*it),x,type,tme);
cord[type].insert(x);
return;
}
if (it==cord[type].begin()){
del_line(mn,(*it),type,tme);
add_line(x,(*it),type,tme);
add_line(mn,x,type,tme);
cord[type].insert(x);
return;
}
int l1,r1=(*it);
it--;
l1=(*it);
del_line(l1,r1,type,tme);
add_line(x,r1,type,tme);
add_line(l1,x,type,tme);
cord[type].insert(x);
return;
}
void del_point(int x,int type,int tme){
if (dubi[type].find(x)!=dubi[type].end()){
dubi[type].erase(dubi[type].find(x));
return;
}
if (sz(cord[type])==1)now--;
cord[type].erase(x);
if (cord[type].empty()){
del_line(mn,x,type,tme);
del_line(x,mx,type,tme);
return;
}
auto it=cord[type].upper_bound(x);
if (it==cord[type].end()){
it--;
del_line((*it),x,type,tme);
del_line(x,mx,type,tme);
add_line((*it),mx,type,tme);
return;
}
if (it==cord[type].begin()){
del_line(mn,x,type,tme);
del_line(x,(*it),type,tme);
add_line(mn,(*it),type,tme);
return;
}
int l1,r1=(*it);
it--;
l1=(*it);
del_line(l1,x,type,tme);
del_line(x,r1,type,tme);
add_line(l1,r1,type,tme);
return;
}
struct store{
int x,t,a,b;
}a[maxn];
pii b[maxn];
vector<int>add[maxn*3],del[maxn*3];
vector<int>answer[maxn*3];
int st1[maxn*4],st2[maxn*4],c[maxn];
/*
1 for a-x
2 for x-a
*/
void build(int id,int l,int r){
st1[id]=mx,st2[id]=mn;
if (l==r)return;
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
}
void upd1(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st1[id]=min(st1[id],val);
return;
}
int mid=(l+r)>>1;
upd1(id<<1,l,mid,u,v,val);
upd1(id<<1|1,mid+1,r,u,v,val);
}
void upd2(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st2[id]=max(st2[id],val);
return;
}
int mid=(l+r)>>1;
upd2(id<<1,l,mid,u,v,val);
upd2(id<<1|1,mid+1,r,u,v,val);
}
pii get(int id,int l,int r,int u){
pii xxx={mx,mn};
while (true){
xxx.fi=min(xxx.fi,st1[id]);
xxx.se=max(xxx.se,st2[id]);
if (l==r)break;
int mid=(l+r)>>1;
if (mid>=u){
id=(id<<1);
r=mid;
}
else {
id=(id<<1|1);
l=mid+1;
}
}
return xxx;
}
void new_home(int id,int l,int r){
if (!st[id].empty()){
vector<int>cc;
for1(i,l,r){
for (auto v:answer[i]){
if (c[v]==-1)continue;
cc.pb(b[v].fi);
}
}
sort(all(cc));
cc.resize(distance(cc.begin(),unique(all(cc))));
if (!cc.empty()){
int m=sz(cc);
build(1,1,m);
for(auto v:st[id]){
int l1=v.fi,r1=v.se,mid=(l1+r1)/2;
l1=lower_bound(all(cc),l1)-cc.begin()+1;
r1=upper_bound(all(cc),r1)-cc.begin();
mid=upper_bound(all(cc),mid)-cc.begin();
upd1(1,1,m,l1,mid,v.fi);
upd2(1,1,m,mid+1,r1,v.se);
}
for1(i,l,r){
for (auto v:answer[i]){
if (c[v]==-1)continue;
int pos=lower_bound(all(cc),b[v].fi)-cc.begin()+1;
pii xxx=get(1,1,m,pos);
c[v]=max({c[v],b[v].fi-xxx.fi,xxx.se-b[v].fi});
}
}
}
}
if (l==r)return;
int mid=(l+r)>>1;
new_home(id<<1,l,mid);
new_home(id<<1|1,mid+1,r);
}
void init(){
    cin>>n>>k>>q;
    for1(i,1,n)cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b;
    for1(i,1,q)cin>>b[i].fi>>b[i].se;
}
void nentime(){
    vector<int>tme;
    for1(i,1,n){
    tme.pb(a[i].a),tme.pb(a[i].b);
    }
    for1(i,1,q){
    tme.pb(b[i].se);
    }
    sort(all(tme));
    tme.resize(distance(tme.begin(),unique(all(tme))));
    map<int,int>nn;
    for1(i,0,sz(tme)-1)nn[tme[i]]=i+1;
    for1(i,1,n){
    a[i].a=nn[a[i].a],a[i].b=nn[a[i].b];
    add[a[i].a].pb(i);
    del[a[i].b].pb(i);
    }
    for1(i,1,q){
    b[i].se=nn[b[i].se];
    answer[b[i].se].pb(i);
    }
    line=sz(tme);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    init();
    nentime();
    for1(i,1,line){
    for (auto v:add[i]){
    add_point(a[v].x,a[v].t,i);
    }
    for (auto v:answer[i]){
    if (now<k){
    c[v]=-1;
    continue;
    }
    }
    for (auto v:del[i]){
    del_point(a[v].x,a[v].t,i+1);
    }
    }
    for1(i,1,k){
    for (auto u:temp[i]){
    update(1,1,line,u.tim,line,{u.l,u.r});
    }
    }
    new_home(1,1,line);
    for1(i,1,q)cout<<c[i]<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 197724 KB Output is correct
2 Correct 41 ms 193612 KB Output is correct
3 Correct 41 ms 193628 KB Output is correct
4 Correct 43 ms 197716 KB Output is correct
5 Correct 42 ms 197716 KB Output is correct
6 Correct 43 ms 197972 KB Output is correct
7 Correct 45 ms 193768 KB Output is correct
8 Correct 43 ms 197916 KB Output is correct
9 Correct 43 ms 197972 KB Output is correct
10 Correct 44 ms 197968 KB Output is correct
11 Correct 43 ms 193868 KB Output is correct
12 Correct 44 ms 198092 KB Output is correct
13 Correct 46 ms 197996 KB Output is correct
14 Correct 43 ms 198220 KB Output is correct
15 Correct 45 ms 197980 KB Output is correct
16 Correct 44 ms 197932 KB Output is correct
17 Correct 45 ms 197972 KB Output is correct
18 Correct 43 ms 197968 KB Output is correct
19 Correct 44 ms 197980 KB Output is correct
20 Correct 43 ms 197880 KB Output is correct
21 Correct 43 ms 197720 KB Output is correct
22 Correct 44 ms 197968 KB Output is correct
23 Correct 44 ms 198232 KB Output is correct
24 Correct 48 ms 197968 KB Output is correct
25 Correct 43 ms 197964 KB Output is correct
26 Correct 45 ms 197852 KB Output is correct
27 Correct 42 ms 197716 KB Output is correct
28 Correct 43 ms 197968 KB Output is correct
29 Correct 43 ms 197972 KB Output is correct
30 Correct 43 ms 197964 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 197724 KB Output is correct
2 Correct 41 ms 193612 KB Output is correct
3 Correct 41 ms 193628 KB Output is correct
4 Correct 43 ms 197716 KB Output is correct
5 Correct 42 ms 197716 KB Output is correct
6 Correct 43 ms 197972 KB Output is correct
7 Correct 45 ms 193768 KB Output is correct
8 Correct 43 ms 197916 KB Output is correct
9 Correct 43 ms 197972 KB Output is correct
10 Correct 44 ms 197968 KB Output is correct
11 Correct 43 ms 193868 KB Output is correct
12 Correct 44 ms 198092 KB Output is correct
13 Correct 46 ms 197996 KB Output is correct
14 Correct 43 ms 198220 KB Output is correct
15 Correct 45 ms 197980 KB Output is correct
16 Correct 44 ms 197932 KB Output is correct
17 Correct 45 ms 197972 KB Output is correct
18 Correct 43 ms 197968 KB Output is correct
19 Correct 44 ms 197980 KB Output is correct
20 Correct 43 ms 197880 KB Output is correct
21 Correct 43 ms 197720 KB Output is correct
22 Correct 44 ms 197968 KB Output is correct
23 Correct 44 ms 198232 KB Output is correct
24 Correct 48 ms 197968 KB Output is correct
25 Correct 43 ms 197964 KB Output is correct
26 Correct 45 ms 197852 KB Output is correct
27 Correct 42 ms 197716 KB Output is correct
28 Correct 43 ms 197968 KB Output is correct
29 Correct 43 ms 197972 KB Output is correct
30 Correct 43 ms 197964 KB Output is correct
31 Correct 942 ms 238336 KB Output is correct
32 Correct 94 ms 200960 KB Output is correct
33 Correct 762 ms 237056 KB Output is correct
34 Correct 853 ms 236780 KB Output is correct
35 Correct 923 ms 238600 KB Output is correct
36 Correct 850 ms 238172 KB Output is correct
37 Correct 608 ms 232688 KB Output is correct
38 Correct 536 ms 232572 KB Output is correct
39 Correct 401 ms 225724 KB Output is correct
40 Correct 426 ms 227584 KB Output is correct
41 Correct 496 ms 230036 KB Output is correct
42 Correct 440 ms 230276 KB Output is correct
43 Correct 77 ms 201256 KB Output is correct
44 Correct 454 ms 229632 KB Output is correct
45 Correct 435 ms 225436 KB Output is correct
46 Correct 300 ms 219456 KB Output is correct
47 Correct 264 ms 218184 KB Output is correct
48 Correct 235 ms 216980 KB Output is correct
49 Correct 279 ms 221056 KB Output is correct
50 Correct 342 ms 227808 KB Output is correct
51 Correct 260 ms 219404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 268308 KB Output is correct
2 Correct 1651 ms 261816 KB Output is correct
3 Correct 1022 ms 275188 KB Output is correct
4 Correct 1188 ms 270064 KB Output is correct
5 Correct 1669 ms 261548 KB Output is correct
6 Correct 1669 ms 262680 KB Output is correct
7 Correct 900 ms 275216 KB Output is correct
8 Correct 956 ms 262756 KB Output is correct
9 Correct 1012 ms 258196 KB Output is correct
10 Correct 1124 ms 256040 KB Output is correct
11 Correct 835 ms 254600 KB Output is correct
12 Correct 857 ms 255816 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4602 ms 329156 KB Output is correct
2 Correct 328 ms 219376 KB Output is correct
3 Correct 4319 ms 328324 KB Output is correct
4 Correct 1407 ms 317516 KB Output is correct
5 Correct 1911 ms 322288 KB Output is correct
6 Correct 1823 ms 321388 KB Output is correct
7 Correct 4159 ms 327076 KB Output is correct
8 Correct 4191 ms 327592 KB Output is correct
9 Correct 1691 ms 317056 KB Output is correct
10 Correct 3457 ms 328676 KB Output is correct
11 Correct 4523 ms 329616 KB Output is correct
12 Correct 4255 ms 329044 KB Output is correct
13 Correct 1760 ms 290016 KB Output is correct
14 Correct 1683 ms 288456 KB Output is correct
15 Correct 2134 ms 299336 KB Output is correct
16 Correct 2628 ms 309652 KB Output is correct
17 Correct 2335 ms 306200 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 197724 KB Output is correct
2 Correct 41 ms 193612 KB Output is correct
3 Correct 41 ms 193628 KB Output is correct
4 Correct 43 ms 197716 KB Output is correct
5 Correct 42 ms 197716 KB Output is correct
6 Correct 43 ms 197972 KB Output is correct
7 Correct 45 ms 193768 KB Output is correct
8 Correct 43 ms 197916 KB Output is correct
9 Correct 43 ms 197972 KB Output is correct
10 Correct 44 ms 197968 KB Output is correct
11 Correct 43 ms 193868 KB Output is correct
12 Correct 44 ms 198092 KB Output is correct
13 Correct 46 ms 197996 KB Output is correct
14 Correct 43 ms 198220 KB Output is correct
15 Correct 45 ms 197980 KB Output is correct
16 Correct 44 ms 197932 KB Output is correct
17 Correct 45 ms 197972 KB Output is correct
18 Correct 43 ms 197968 KB Output is correct
19 Correct 44 ms 197980 KB Output is correct
20 Correct 43 ms 197880 KB Output is correct
21 Correct 43 ms 197720 KB Output is correct
22 Correct 44 ms 197968 KB Output is correct
23 Correct 44 ms 198232 KB Output is correct
24 Correct 48 ms 197968 KB Output is correct
25 Correct 43 ms 197964 KB Output is correct
26 Correct 45 ms 197852 KB Output is correct
27 Correct 42 ms 197716 KB Output is correct
28 Correct 43 ms 197968 KB Output is correct
29 Correct 43 ms 197972 KB Output is correct
30 Correct 43 ms 197964 KB Output is correct
31 Correct 942 ms 238336 KB Output is correct
32 Correct 94 ms 200960 KB Output is correct
33 Correct 762 ms 237056 KB Output is correct
34 Correct 853 ms 236780 KB Output is correct
35 Correct 923 ms 238600 KB Output is correct
36 Correct 850 ms 238172 KB Output is correct
37 Correct 608 ms 232688 KB Output is correct
38 Correct 536 ms 232572 KB Output is correct
39 Correct 401 ms 225724 KB Output is correct
40 Correct 426 ms 227584 KB Output is correct
41 Correct 496 ms 230036 KB Output is correct
42 Correct 440 ms 230276 KB Output is correct
43 Correct 77 ms 201256 KB Output is correct
44 Correct 454 ms 229632 KB Output is correct
45 Correct 435 ms 225436 KB Output is correct
46 Correct 300 ms 219456 KB Output is correct
47 Correct 264 ms 218184 KB Output is correct
48 Correct 235 ms 216980 KB Output is correct
49 Correct 279 ms 221056 KB Output is correct
50 Correct 342 ms 227808 KB Output is correct
51 Correct 260 ms 219404 KB Output is correct
52 Correct 324 ms 226308 KB Output is correct
53 Correct 339 ms 225052 KB Output is correct
54 Correct 411 ms 235584 KB Output is correct
55 Correct 506 ms 230652 KB Output is correct
56 Correct 508 ms 230748 KB Output is correct
57 Correct 513 ms 229376 KB Output is correct
58 Correct 472 ms 229804 KB Output is correct
59 Correct 477 ms 230396 KB Output is correct
60 Correct 472 ms 228860 KB Output is correct
61 Correct 88 ms 207008 KB Output is correct
62 Correct 404 ms 233312 KB Output is correct
63 Correct 588 ms 234816 KB Output is correct
64 Correct 702 ms 236096 KB Output is correct
65 Correct 731 ms 235772 KB Output is correct
66 Correct 538 ms 230400 KB Output is correct
67 Correct 155 ms 206844 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 197724 KB Output is correct
2 Correct 41 ms 193612 KB Output is correct
3 Correct 41 ms 193628 KB Output is correct
4 Correct 43 ms 197716 KB Output is correct
5 Correct 42 ms 197716 KB Output is correct
6 Correct 43 ms 197972 KB Output is correct
7 Correct 45 ms 193768 KB Output is correct
8 Correct 43 ms 197916 KB Output is correct
9 Correct 43 ms 197972 KB Output is correct
10 Correct 44 ms 197968 KB Output is correct
11 Correct 43 ms 193868 KB Output is correct
12 Correct 44 ms 198092 KB Output is correct
13 Correct 46 ms 197996 KB Output is correct
14 Correct 43 ms 198220 KB Output is correct
15 Correct 45 ms 197980 KB Output is correct
16 Correct 44 ms 197932 KB Output is correct
17 Correct 45 ms 197972 KB Output is correct
18 Correct 43 ms 197968 KB Output is correct
19 Correct 44 ms 197980 KB Output is correct
20 Correct 43 ms 197880 KB Output is correct
21 Correct 43 ms 197720 KB Output is correct
22 Correct 44 ms 197968 KB Output is correct
23 Correct 44 ms 198232 KB Output is correct
24 Correct 48 ms 197968 KB Output is correct
25 Correct 43 ms 197964 KB Output is correct
26 Correct 45 ms 197852 KB Output is correct
27 Correct 42 ms 197716 KB Output is correct
28 Correct 43 ms 197968 KB Output is correct
29 Correct 43 ms 197972 KB Output is correct
30 Correct 43 ms 197964 KB Output is correct
31 Correct 942 ms 238336 KB Output is correct
32 Correct 94 ms 200960 KB Output is correct
33 Correct 762 ms 237056 KB Output is correct
34 Correct 853 ms 236780 KB Output is correct
35 Correct 923 ms 238600 KB Output is correct
36 Correct 850 ms 238172 KB Output is correct
37 Correct 608 ms 232688 KB Output is correct
38 Correct 536 ms 232572 KB Output is correct
39 Correct 401 ms 225724 KB Output is correct
40 Correct 426 ms 227584 KB Output is correct
41 Correct 496 ms 230036 KB Output is correct
42 Correct 440 ms 230276 KB Output is correct
43 Correct 77 ms 201256 KB Output is correct
44 Correct 454 ms 229632 KB Output is correct
45 Correct 435 ms 225436 KB Output is correct
46 Correct 300 ms 219456 KB Output is correct
47 Correct 264 ms 218184 KB Output is correct
48 Correct 235 ms 216980 KB Output is correct
49 Correct 279 ms 221056 KB Output is correct
50 Correct 342 ms 227808 KB Output is correct
51 Correct 260 ms 219404 KB Output is correct
52 Correct 1269 ms 268308 KB Output is correct
53 Correct 1651 ms 261816 KB Output is correct
54 Correct 1022 ms 275188 KB Output is correct
55 Correct 1188 ms 270064 KB Output is correct
56 Correct 1669 ms 261548 KB Output is correct
57 Correct 1669 ms 262680 KB Output is correct
58 Correct 900 ms 275216 KB Output is correct
59 Correct 956 ms 262756 KB Output is correct
60 Correct 1012 ms 258196 KB Output is correct
61 Correct 1124 ms 256040 KB Output is correct
62 Correct 835 ms 254600 KB Output is correct
63 Correct 857 ms 255816 KB Output is correct
64 Correct 4602 ms 329156 KB Output is correct
65 Correct 328 ms 219376 KB Output is correct
66 Correct 4319 ms 328324 KB Output is correct
67 Correct 1407 ms 317516 KB Output is correct
68 Correct 1911 ms 322288 KB Output is correct
69 Correct 1823 ms 321388 KB Output is correct
70 Correct 4159 ms 327076 KB Output is correct
71 Correct 4191 ms 327592 KB Output is correct
72 Correct 1691 ms 317056 KB Output is correct
73 Correct 3457 ms 328676 KB Output is correct
74 Correct 4523 ms 329616 KB Output is correct
75 Correct 4255 ms 329044 KB Output is correct
76 Correct 1760 ms 290016 KB Output is correct
77 Correct 1683 ms 288456 KB Output is correct
78 Correct 2134 ms 299336 KB Output is correct
79 Correct 2628 ms 309652 KB Output is correct
80 Correct 2335 ms 306200 KB Output is correct
81 Correct 324 ms 226308 KB Output is correct
82 Correct 339 ms 225052 KB Output is correct
83 Correct 411 ms 235584 KB Output is correct
84 Correct 506 ms 230652 KB Output is correct
85 Correct 508 ms 230748 KB Output is correct
86 Correct 513 ms 229376 KB Output is correct
87 Correct 472 ms 229804 KB Output is correct
88 Correct 477 ms 230396 KB Output is correct
89 Correct 472 ms 228860 KB Output is correct
90 Correct 88 ms 207008 KB Output is correct
91 Correct 404 ms 233312 KB Output is correct
92 Correct 588 ms 234816 KB Output is correct
93 Correct 702 ms 236096 KB Output is correct
94 Correct 731 ms 235772 KB Output is correct
95 Correct 538 ms 230400 KB Output is correct
96 Correct 155 ms 206844 KB Output is correct
97 Correct 2377 ms 375476 KB Output is correct
98 Correct 330 ms 211952 KB Output is correct
99 Execution timed out 5015 ms 391348 KB Time limit exceeded
100 Halted 0 ms 0 KB -