oj.uz

Submission #972786

# Submission time Handle Problem Language Result Execution time Memory
972786 2024-05-01T07:23:34 Z bachhoangxuan New Home (APIO18_new_home) C++17
100 / 100
 2799 ms 106308 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e8;
const int mod=998244353;
const int maxn=300005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=101;

int n,k,q,sz,res[maxn];
vector<int> com;
vector<piii> cc;
multiset<int> ss[maxn],rr[maxn];

int Max[4*maxn];
void update(int l,int r,int id,int p){
    if(l==r){
        Max[id]=(rr[l].empty()?0:*rr[l].rbegin());
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,id<<1,p);
    else update(mid+1,r,id<<1|1,p);
    Max[id]=max(Max[id<<1],Max[id<<1|1]);
}
int query(int l,int r,int id,int p){
    if(l==r) return Max[id];
    int mid=(l+r)>>1;
    if(p<=mid) return query(l,mid,id<<1,p);
    else return max(Max[id<<1],query(mid+1,r,id<<1|1,p));
}

void add_range(int l,int r){
    int pos=lower_bound(com.begin(),com.end(),l)-com.begin()+1;
    //cout << "add_range " << l << ' ' << r << ' ' << pos << endl;
    rr[pos].insert(r);
    update(1,sz,1,pos);
}

void del_range(int l,int r){
    int pos=lower_bound(com.begin(),com.end(),l)-com.begin()+1;
    //cout << "del_rane " << l << ' ' << r << ' ' << pos << endl;
    rr[pos].erase(rr[pos].find(r));
    update(1,sz,1,pos);
}

void add(int t,int x){
    //cout << "add " << t << ' ' << x << '\n';
    auto it=ss[t].lower_bound(x);
    int l=1,r=(it==ss[t].end()?inf:*it-1);
    if(it!=ss[t].begin()) it--,l=*it+1;
    del_range(l,r);
    add_range(l,x-1);
    add_range(x+1,r);
    ss[t].insert(x);
}

void del(int t,int x){
    auto it=ss[t].lower_bound(x);
    it=ss[t].erase(it);
    int l=1,r=(it==ss[t].end()?inf:*it-1);
    if(it!=ss[t].begin()) it--,l=*it+1;
    del_range(l,x-1);
    del_range(x+1,r);
    add_range(l,r);
}

int query(int x){
    int l=0,r=max(inf-x,x),ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        int L=max(x-mid,1),R=min(x+mid,inf);
        int pos=upper_bound(com.begin(),com.end(),L)-com.begin();
        int val=query(1,sz,1,pos);
        if(R<=val) l=mid+1;
        else ans=mid,r=mid-1;
    }
    return ans;
}

void solve(){
    cin >> n >> k >> q;
    com.push_back(1);
    for(int i=1;i<=n;i++){
        int x,t,a,b;cin >> x >> t >> a >> b;
        com.push_back(x+1);
        cc.push_back({a,{t,x}});
        cc.push_back({b+1,{-t,x}});
    }
    for(int i=1;i<=q;i++){
        int l,y;cin >> l >> y;
        cc.push_back({y,{inf+i,l}});
    }
    sort(cc.begin(),cc.end());
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    sz=(int)com.size();
    for(int i=1;i<=k;i++) rr[1].insert(inf);
    update(1,sz,1,1);
    for(auto [_,p]:cc){
        auto [t,x]=p;
        if(t<0) del(-t,x);
        else if(t<=k) add(t,x);
        else{
            t-=inf;
            res[t]=query(x);
        }
    }
    for(int i=1;i<=q;i++) cout << res[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29136 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 8 ms 29020 KB Output is correct
6 Correct 8 ms 29024 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29268 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29020 KB Output is correct
15 Correct 7 ms 29016 KB Output is correct
16 Correct 7 ms 29276 KB Output is correct
17 Correct 7 ms 29020 KB Output is correct
18 Correct 7 ms 29276 KB Output is correct
19 Correct 7 ms 29276 KB Output is correct
20 Correct 9 ms 29208 KB Output is correct
21 Correct 7 ms 29276 KB Output is correct
22 Correct 7 ms 29276 KB Output is correct
23 Correct 7 ms 29276 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 8 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 7 ms 29016 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Correct 7 ms 29020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29136 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 8 ms 29020 KB Output is correct
6 Correct 8 ms 29024 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29268 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29020 KB Output is correct
15 Correct 7 ms 29016 KB Output is correct
16 Correct 7 ms 29276 KB Output is correct
17 Correct 7 ms 29020 KB Output is correct
18 Correct 7 ms 29276 KB Output is correct
19 Correct 7 ms 29276 KB Output is correct
20 Correct 9 ms 29208 KB Output is correct
21 Correct 7 ms 29276 KB Output is correct
22 Correct 7 ms 29276 KB Output is correct
23 Correct 7 ms 29276 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 8 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 7 ms 29016 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Correct 7 ms 29020 KB Output is correct
31 Correct 356 ms 43428 KB Output is correct
32 Correct 95 ms 35200 KB Output is correct
33 Correct 352 ms 38980 KB Output is correct
34 Correct 327 ms 39304 KB Output is correct
35 Correct 359 ms 42744 KB Output is correct
36 Correct 362 ms 43132 KB Output is correct
37 Correct 334 ms 37500 KB Output is correct
38 Correct 319 ms 38012 KB Output is correct
39 Correct 279 ms 37884 KB Output is correct
40 Correct 299 ms 38428 KB Output is correct
41 Correct 228 ms 37688 KB Output is correct
42 Correct 214 ms 37368 KB Output is correct
43 Correct 84 ms 39928 KB Output is correct
44 Correct 242 ms 37572 KB Output is correct
45 Correct 231 ms 37528 KB Output is correct
46 Correct 249 ms 37480 KB Output is correct
47 Correct 214 ms 37376 KB Output is correct
48 Correct 203 ms 36856 KB Output is correct
49 Correct 253 ms 37048 KB Output is correct
50 Correct 215 ms 37760 KB Output is correct
51 Correct 245 ms 37116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 80536 KB Output is correct
2 Correct 1870 ms 88276 KB Output is correct
3 Correct 1579 ms 105900 KB Output is correct
4 Correct 1405 ms 96600 KB Output is correct
5 Correct 1789 ms 89572 KB Output is correct
6 Correct 1827 ms 88252 KB Output is correct
7 Correct 1560 ms 105204 KB Output is correct
8 Correct 1430 ms 97252 KB Output is correct
9 Correct 1506 ms 92228 KB Output is correct
10 Correct 1905 ms 90732 KB Output is correct
11 Correct 1554 ms 89500 KB Output is correct
12 Correct 1614 ms 90380 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2001 ms 77016 KB Output is correct
2 Correct 518 ms 75364 KB Output is correct
3 Correct 2300 ms 89856 KB Output is correct
4 Correct 2007 ms 103424 KB Output is correct
5 Correct 1664 ms 92352 KB Output is correct
6 Correct 1708 ms 94688 KB Output is correct
7 Correct 2359 ms 87912 KB Output is correct
8 Correct 2330 ms 88856 KB Output is correct
9 Correct 1976 ms 104316 KB Output is correct
10 Correct 1712 ms 93372 KB Output is correct
11 Correct 1849 ms 92484 KB Output is correct
12 Correct 2301 ms 90604 KB Output is correct
13 Correct 1495 ms 87244 KB Output is correct
14 Correct 1447 ms 86068 KB Output is correct
15 Correct 1719 ms 87532 KB Output is correct
16 Correct 1787 ms 88836 KB Output is correct
17 Correct 1702 ms 87020 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29136 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 8 ms 29020 KB Output is correct
6 Correct 8 ms 29024 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29268 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29020 KB Output is correct
15 Correct 7 ms 29016 KB Output is correct
16 Correct 7 ms 29276 KB Output is correct
17 Correct 7 ms 29020 KB Output is correct
18 Correct 7 ms 29276 KB Output is correct
19 Correct 7 ms 29276 KB Output is correct
20 Correct 9 ms 29208 KB Output is correct
21 Correct 7 ms 29276 KB Output is correct
22 Correct 7 ms 29276 KB Output is correct
23 Correct 7 ms 29276 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 8 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 7 ms 29016 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Correct 7 ms 29020 KB Output is correct
31 Correct 356 ms 43428 KB Output is correct
32 Correct 95 ms 35200 KB Output is correct
33 Correct 352 ms 38980 KB Output is correct
34 Correct 327 ms 39304 KB Output is correct
35 Correct 359 ms 42744 KB Output is correct
36 Correct 362 ms 43132 KB Output is correct
37 Correct 334 ms 37500 KB Output is correct
38 Correct 319 ms 38012 KB Output is correct
39 Correct 279 ms 37884 KB Output is correct
40 Correct 299 ms 38428 KB Output is correct
41 Correct 228 ms 37688 KB Output is correct
42 Correct 214 ms 37368 KB Output is correct
43 Correct 84 ms 39928 KB Output is correct
44 Correct 242 ms 37572 KB Output is correct
45 Correct 231 ms 37528 KB Output is correct
46 Correct 249 ms 37480 KB Output is correct
47 Correct 214 ms 37376 KB Output is correct
48 Correct 203 ms 36856 KB Output is correct
49 Correct 253 ms 37048 KB Output is correct
50 Correct 215 ms 37760 KB Output is correct
51 Correct 245 ms 37116 KB Output is correct
52 Correct 261 ms 45732 KB Output is correct
53 Correct 244 ms 42392 KB Output is correct
54 Correct 252 ms 43564 KB Output is correct
55 Correct 249 ms 40696 KB Output is correct
56 Correct 271 ms 41468 KB Output is correct
57 Correct 230 ms 38140 KB Output is correct
58 Correct 232 ms 40972 KB Output is correct
59 Correct 239 ms 42176 KB Output is correct
60 Correct 253 ms 38084 KB Output is correct
61 Correct 123 ms 42868 KB Output is correct
62 Correct 252 ms 46620 KB Output is correct
63 Correct 261 ms 43388 KB Output is correct
64 Correct 275 ms 42680 KB Output is correct
65 Correct 244 ms 38904 KB Output is correct
66 Correct 221 ms 38140 KB Output is correct
67 Correct 138 ms 34452 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29016 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29136 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 8 ms 29020 KB Output is correct
6 Correct 8 ms 29024 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29268 KB Output is correct
12 Correct 8 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29020 KB Output is correct
15 Correct 7 ms 29016 KB Output is correct
16 Correct 7 ms 29276 KB Output is correct
17 Correct 7 ms 29020 KB Output is correct
18 Correct 7 ms 29276 KB Output is correct
19 Correct 7 ms 29276 KB Output is correct
20 Correct 9 ms 29208 KB Output is correct
21 Correct 7 ms 29276 KB Output is correct
22 Correct 7 ms 29276 KB Output is correct
23 Correct 7 ms 29276 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 8 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 7 ms 29016 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Correct 7 ms 29020 KB Output is correct
31 Correct 356 ms 43428 KB Output is correct
32 Correct 95 ms 35200 KB Output is correct
33 Correct 352 ms 38980 KB Output is correct
34 Correct 327 ms 39304 KB Output is correct
35 Correct 359 ms 42744 KB Output is correct
36 Correct 362 ms 43132 KB Output is correct
37 Correct 334 ms 37500 KB Output is correct
38 Correct 319 ms 38012 KB Output is correct
39 Correct 279 ms 37884 KB Output is correct
40 Correct 299 ms 38428 KB Output is correct
41 Correct 228 ms 37688 KB Output is correct
42 Correct 214 ms 37368 KB Output is correct
43 Correct 84 ms 39928 KB Output is correct
44 Correct 242 ms 37572 KB Output is correct
45 Correct 231 ms 37528 KB Output is correct
46 Correct 249 ms 37480 KB Output is correct
47 Correct 214 ms 37376 KB Output is correct
48 Correct 203 ms 36856 KB Output is correct
49 Correct 253 ms 37048 KB Output is correct
50 Correct 215 ms 37760 KB Output is correct
51 Correct 245 ms 37116 KB Output is correct
52 Correct 1363 ms 80536 KB Output is correct
53 Correct 1870 ms 88276 KB Output is correct
54 Correct 1579 ms 105900 KB Output is correct
55 Correct 1405 ms 96600 KB Output is correct
56 Correct 1789 ms 89572 KB Output is correct
57 Correct 1827 ms 88252 KB Output is correct
58 Correct 1560 ms 105204 KB Output is correct
59 Correct 1430 ms 97252 KB Output is correct
60 Correct 1506 ms 92228 KB Output is correct
61 Correct 1905 ms 90732 KB Output is correct
62 Correct 1554 ms 89500 KB Output is correct
63 Correct 1614 ms 90380 KB Output is correct
64 Correct 2001 ms 77016 KB Output is correct
65 Correct 518 ms 75364 KB Output is correct
66 Correct 2300 ms 89856 KB Output is correct
67 Correct 2007 ms 103424 KB Output is correct
68 Correct 1664 ms 92352 KB Output is correct
69 Correct 1708 ms 94688 KB Output is correct
70 Correct 2359 ms 87912 KB Output is correct
71 Correct 2330 ms 88856 KB Output is correct
72 Correct 1976 ms 104316 KB Output is correct
73 Correct 1712 ms 93372 KB Output is correct
74 Correct 1849 ms 92484 KB Output is correct
75 Correct 2301 ms 90604 KB Output is correct
76 Correct 1495 ms 87244 KB Output is correct
77 Correct 1447 ms 86068 KB Output is correct
78 Correct 1719 ms 87532 KB Output is correct
79 Correct 1787 ms 88836 KB Output is correct
80 Correct 1702 ms 87020 KB Output is correct
81 Correct 261 ms 45732 KB Output is correct
82 Correct 244 ms 42392 KB Output is correct
83 Correct 252 ms 43564 KB Output is correct
84 Correct 249 ms 40696 KB Output is correct
85 Correct 271 ms 41468 KB Output is correct
86 Correct 230 ms 38140 KB Output is correct
87 Correct 232 ms 40972 KB Output is correct
88 Correct 239 ms 42176 KB Output is correct
89 Correct 253 ms 38084 KB Output is correct
90 Correct 123 ms 42868 KB Output is correct
91 Correct 252 ms 46620 KB Output is correct
92 Correct 261 ms 43388 KB Output is correct
93 Correct 275 ms 42680 KB Output is correct
94 Correct 244 ms 38904 KB Output is correct
95 Correct 221 ms 38140 KB Output is correct
96 Correct 138 ms 34452 KB Output is correct
97 Correct 1973 ms 104796 KB Output is correct
98 Correct 455 ms 58860 KB Output is correct
99 Correct 2500 ms 72660 KB Output is correct
100 Correct 1819 ms 88912 KB Output is correct
101 Correct 1987 ms 97012 KB Output is correct
102 Correct 2799 ms 90252 KB Output is correct
103 Correct 1924 ms 66100 KB Output is correct
104 Correct 1984 ms 65232 KB Output is correct
105 Correct 1692 ms 64556 KB Output is correct
106 Correct 1733 ms 65080 KB Output is correct
107 Correct 1516 ms 79780 KB Output is correct
108 Correct 1596 ms 86316 KB Output is correct
109 Correct 1395 ms 69512 KB Output is correct
110 Correct 1546 ms 79420 KB Output is correct
111 Correct 1669 ms 84884 KB Output is correct
112 Correct 1381 ms 68760 KB Output is correct
113 Correct 569 ms 100768 KB Output is correct
114 Correct 1935 ms 106308 KB Output is correct
115 Correct 2001 ms 93972 KB Output is correct
116 Correct 1887 ms 86800 KB Output is correct
117 Correct 1732 ms 72912 KB Output is correct
118 Correct 1365 ms 66796 KB Output is correct
119 Correct 898 ms 59156 KB Output is correct
120 Correct 1002 ms 62900 KB Output is correct
121 Correct 1218 ms 65060 KB Output is correct
122 Correct 1272 ms 65380 KB Output is correct
123 Correct 1298 ms 65684 KB Output is correct
124 Correct 1289 ms 65496 KB Output is correct
125 Correct 1443 ms 65036 KB Output is correct
126 Correct 1253 ms 66088 KB Output is correct