oj.uz

Submission #1008334

# Submission time Handle Problem Language Result Execution time Memory
1008334 2024-06-26T09:33:29 Z LonlyR New Home (APIO18_new_home) C++17
47 / 100
 380 ms 101176 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){
//    cout << l << " " << r << " fuckk\n";
    int pos=lower_bound(com.begin(),com.end(),l)-com.begin()+1;
    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;
    rr[pos].erase(rr[pos].find(r));
    update(1,sz,1,pos);
}

void add(int t,int x){
    /// divide segment [l, r] into segment[l, x - 1], [x + 1, r]
    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){
    /// merge segment[l, x - 1], [x + 1, r] in to segment [l, r]
    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}}),
        com.emplace_back(l);
    }
    sort(cc.begin(),cc.end());
    /// compress
    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);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 28764 KB Output is correct
2 Correct 9 ms 28764 KB Output is correct
3 Correct 8 ms 28764 KB Output is correct
4 Correct 8 ms 28764 KB Output is correct
5 Correct 8 ms 28764 KB Output is correct
6 Correct 11 ms 28760 KB Output is correct
7 Correct 9 ms 29276 KB Output is correct
8 Correct 11 ms 28764 KB Output is correct
9 Correct 9 ms 29272 KB Output is correct
10 Correct 9 ms 28760 KB Output is correct
11 Correct 10 ms 28788 KB Output is correct
12 Correct 9 ms 28764 KB Output is correct
13 Correct 10 ms 28764 KB Output is correct
14 Correct 9 ms 29020 KB Output is correct
15 Correct 9 ms 28760 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 12 ms 28764 KB Output is correct
18 Correct 9 ms 29152 KB Output is correct
19 Correct 9 ms 28764 KB Output is correct
20 Correct 9 ms 29276 KB Output is correct
21 Correct 13 ms 28788 KB Output is correct
22 Correct 9 ms 28764 KB Output is correct
23 Correct 10 ms 29276 KB Output is correct
24 Correct 9 ms 28712 KB Output is correct
25 Correct 8 ms 28764 KB Output is correct
26 Correct 9 ms 28764 KB Output is correct
27 Correct 8 ms 29200 KB Output is correct
28 Correct 9 ms 28848 KB Output is correct
29 Correct 11 ms 28764 KB Output is correct
30 Correct 9 ms 28764 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 28764 KB Output is correct
2 Correct 9 ms 28764 KB Output is correct
3 Correct 8 ms 28764 KB Output is correct
4 Correct 8 ms 28764 KB Output is correct
5 Correct 8 ms 28764 KB Output is correct
6 Correct 11 ms 28760 KB Output is correct
7 Correct 9 ms 29276 KB Output is correct
8 Correct 11 ms 28764 KB Output is correct
9 Correct 9 ms 29272 KB Output is correct
10 Correct 9 ms 28760 KB Output is correct
11 Correct 10 ms 28788 KB Output is correct
12 Correct 9 ms 28764 KB Output is correct
13 Correct 10 ms 28764 KB Output is correct
14 Correct 9 ms 29020 KB Output is correct
15 Correct 9 ms 28760 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 12 ms 28764 KB Output is correct
18 Correct 9 ms 29152 KB Output is correct
19 Correct 9 ms 28764 KB Output is correct
20 Correct 9 ms 29276 KB Output is correct
21 Correct 13 ms 28788 KB Output is correct
22 Correct 9 ms 28764 KB Output is correct
23 Correct 10 ms 29276 KB Output is correct
24 Correct 9 ms 28712 KB Output is correct
25 Correct 8 ms 28764 KB Output is correct
26 Correct 9 ms 28764 KB Output is correct
27 Correct 8 ms 29200 KB Output is correct
28 Correct 9 ms 28848 KB Output is correct
29 Correct 11 ms 28764 KB Output is correct
30 Correct 9 ms 28764 KB Output is correct
31 Correct 380 ms 41360 KB Output is correct
32 Correct 89 ms 35068 KB Output is correct
33 Correct 345 ms 37624 KB Output is correct
34 Correct 315 ms 38140 KB Output is correct
35 Correct 362 ms 41700 KB Output is correct
36 Correct 375 ms 41136 KB Output is correct
37 Correct 310 ms 36092 KB Output is correct
38 Correct 314 ms 36008 KB Output is correct
39 Correct 241 ms 36096 KB Output is correct
40 Correct 263 ms 36088 KB Output is correct
41 Correct 221 ms 36860 KB Output is correct
42 Correct 211 ms 36120 KB Output is correct
43 Correct 82 ms 39932 KB Output is correct
44 Correct 214 ms 36400 KB Output is correct
45 Correct 227 ms 36860 KB Output is correct
46 Correct 228 ms 36348 KB Output is correct
47 Correct 174 ms 35832 KB Output is correct
48 Correct 225 ms 35844 KB Output is correct
49 Correct 212 ms 36352 KB Output is correct
50 Correct 205 ms 36608 KB Output is correct
51 Correct 221 ms 36440 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 274 ms 100832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 267 ms 101176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 28764 KB Output is correct
2 Correct 9 ms 28764 KB Output is correct
3 Correct 8 ms 28764 KB Output is correct
4 Correct 8 ms 28764 KB Output is correct
5 Correct 8 ms 28764 KB Output is correct
6 Correct 11 ms 28760 KB Output is correct
7 Correct 9 ms 29276 KB Output is correct
8 Correct 11 ms 28764 KB Output is correct
9 Correct 9 ms 29272 KB Output is correct
10 Correct 9 ms 28760 KB Output is correct
11 Correct 10 ms 28788 KB Output is correct
12 Correct 9 ms 28764 KB Output is correct
13 Correct 10 ms 28764 KB Output is correct
14 Correct 9 ms 29020 KB Output is correct
15 Correct 9 ms 28760 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 12 ms 28764 KB Output is correct
18 Correct 9 ms 29152 KB Output is correct
19 Correct 9 ms 28764 KB Output is correct
20 Correct 9 ms 29276 KB Output is correct
21 Correct 13 ms 28788 KB Output is correct
22 Correct 9 ms 28764 KB Output is correct
23 Correct 10 ms 29276 KB Output is correct
24 Correct 9 ms 28712 KB Output is correct
25 Correct 8 ms 28764 KB Output is correct
26 Correct 9 ms 28764 KB Output is correct
27 Correct 8 ms 29200 KB Output is correct
28 Correct 9 ms 28848 KB Output is correct
29 Correct 11 ms 28764 KB Output is correct
30 Correct 9 ms 28764 KB Output is correct
31 Correct 380 ms 41360 KB Output is correct
32 Correct 89 ms 35068 KB Output is correct
33 Correct 345 ms 37624 KB Output is correct
34 Correct 315 ms 38140 KB Output is correct
35 Correct 362 ms 41700 KB Output is correct
36 Correct 375 ms 41136 KB Output is correct
37 Correct 310 ms 36092 KB Output is correct
38 Correct 314 ms 36008 KB Output is correct
39 Correct 241 ms 36096 KB Output is correct
40 Correct 263 ms 36088 KB Output is correct
41 Correct 221 ms 36860 KB Output is correct
42 Correct 211 ms 36120 KB Output is correct
43 Correct 82 ms 39932 KB Output is correct
44 Correct 214 ms 36400 KB Output is correct
45 Correct 227 ms 36860 KB Output is correct
46 Correct 228 ms 36348 KB Output is correct
47 Correct 174 ms 35832 KB Output is correct
48 Correct 225 ms 35844 KB Output is correct
49 Correct 212 ms 36352 KB Output is correct
50 Correct 205 ms 36608 KB Output is correct
51 Correct 221 ms 36440 KB Output is correct
52 Correct 312 ms 44560 KB Output is correct
53 Correct 268 ms 40960 KB Output is correct
54 Correct 295 ms 42488 KB Output is correct
55 Correct 249 ms 39332 KB Output is correct
56 Correct 276 ms 40700 KB Output is correct
57 Correct 248 ms 37112 KB Output is correct
58 Correct 289 ms 39128 KB Output is correct
59 Correct 276 ms 40460 KB Output is correct
60 Correct 234 ms 37120 KB Output is correct
61 Correct 96 ms 43260 KB Output is correct
62 Correct 281 ms 44548 KB Output is correct
63 Correct 235 ms 42236 KB Output is correct
64 Correct 234 ms 40832 KB Output is correct
65 Correct 239 ms 37888 KB Output is correct
66 Correct 238 ms 36860 KB Output is correct
67 Correct 133 ms 34812 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 28764 KB Output is correct
2 Correct 9 ms 28764 KB Output is correct
3 Correct 8 ms 28764 KB Output is correct
4 Correct 8 ms 28764 KB Output is correct
5 Correct 8 ms 28764 KB Output is correct
6 Correct 11 ms 28760 KB Output is correct
7 Correct 9 ms 29276 KB Output is correct
8 Correct 11 ms 28764 KB Output is correct
9 Correct 9 ms 29272 KB Output is correct
10 Correct 9 ms 28760 KB Output is correct
11 Correct 10 ms 28788 KB Output is correct
12 Correct 9 ms 28764 KB Output is correct
13 Correct 10 ms 28764 KB Output is correct
14 Correct 9 ms 29020 KB Output is correct
15 Correct 9 ms 28760 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 12 ms 28764 KB Output is correct
18 Correct 9 ms 29152 KB Output is correct
19 Correct 9 ms 28764 KB Output is correct
20 Correct 9 ms 29276 KB Output is correct
21 Correct 13 ms 28788 KB Output is correct
22 Correct 9 ms 28764 KB Output is correct
23 Correct 10 ms 29276 KB Output is correct
24 Correct 9 ms 28712 KB Output is correct
25 Correct 8 ms 28764 KB Output is correct
26 Correct 9 ms 28764 KB Output is correct
27 Correct 8 ms 29200 KB Output is correct
28 Correct 9 ms 28848 KB Output is correct
29 Correct 11 ms 28764 KB Output is correct
30 Correct 9 ms 28764 KB Output is correct
31 Correct 380 ms 41360 KB Output is correct
32 Correct 89 ms 35068 KB Output is correct
33 Correct 345 ms 37624 KB Output is correct
34 Correct 315 ms 38140 KB Output is correct
35 Correct 362 ms 41700 KB Output is correct
36 Correct 375 ms 41136 KB Output is correct
37 Correct 310 ms 36092 KB Output is correct
38 Correct 314 ms 36008 KB Output is correct
39 Correct 241 ms 36096 KB Output is correct
40 Correct 263 ms 36088 KB Output is correct
41 Correct 221 ms 36860 KB Output is correct
42 Correct 211 ms 36120 KB Output is correct
43 Correct 82 ms 39932 KB Output is correct
44 Correct 214 ms 36400 KB Output is correct
45 Correct 227 ms 36860 KB Output is correct
46 Correct 228 ms 36348 KB Output is correct
47 Correct 174 ms 35832 KB Output is correct
48 Correct 225 ms 35844 KB Output is correct
49 Correct 212 ms 36352 KB Output is correct
50 Correct 205 ms 36608 KB Output is correct
51 Correct 221 ms 36440 KB Output is correct
52 Runtime error 274 ms 100832 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -