oj.uz

답안 #735253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735253 2023-05-03T18:40:11 Z socpite 새 집 (APIO18_new_home) C++14
57 / 100
 5000 ms 814984 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
 
#define f first 
#define s second
 
typedef long long ll;
 
const int inf = 1e8+5;
const int maxn = 3e5+5;
 
vector<int> posq;
int n, K, q;
 
int X[maxn], T[maxn], A[maxn], B[maxn], L[maxn], Y[maxn], ans[maxn], td[maxn][2];
int pc[inf];

int lb(int x){return pc[x-1];}
int ub(int x){return pc[x];}

int etype[maxn];
 
int tot;
 
set<pair<int, int>> lmao[maxn];
priority_queue<pair<int, pair<int, int>>> st[4*maxn][2];
 
void _add(int l, int r, int ql, int qr, pair<int, int> k, int ty, int id){
    //cout << ql << " " << qr << " " << ty << endl;
    if(ql > qr)return;
    if(l > qr || ql > r)return;
    else if(ql <= l && r <= qr){
        //cout << "a " << id << " " << ty << endl;
        if(!ty)st[id][ty].push({-k.f, {k.s, td[k.s][ty]}});
        else st[id][ty].push({k.f, {k.s, td[k.s][ty]}});
    }
    else {
        int mid = (l+r)>>1;
        _add(l, mid, ql, qr, k, ty, id<<1);
        _add(mid+1, r, ql, qr, k, ty, id<<1|1);
    }
}
 
int _query(int l, int r, int k, int id){
    //cout << l << " " << r << " " << id << endl;
    if(tot != K)return -1;
    int re = 0;
    while(!st[id][0].empty()){
        auto x = st[id][0].top();
        if(td[x.s.f][0] != x.s.s)st[id][0].pop();
        else break;
    }
    while(!st[id][1].empty()){
        auto x = st[id][1].top();
        if(td[x.s.f][1] != x.s.s)st[id][1].pop();
        else break;
    }
    if(!st[id][0].empty())re = max(re, posq[k] + st[id][0].top().f);
    if(!st[id][1].empty())re = max(re, st[id][1].top().f - posq[k]);
    if(l == r)return re;
    int mid = (l+r)>>1;
    if(k <= mid)re = max(re, _query(l, mid, k, id<<1));
    else re = max(re, _query(mid+1, r, k, id<<1|1));
    return re;
}
 
int query(int id){
    return _query(0, posq.size()-1, lb(L[id]), 1);    
}
 
void add(int ql, int qr, pair<int, int> k, int ty){
    _add(0, posq.size()-1, lb(ql), ub(qr)-1, k, ty, 1);
}
 
 
void s_add(set<pair<int, int>>::iterator it, int ty){
    int id = it->s;
    if(ty == 0){
        if(next(it) == lmao[T[id]].end())add(X[id]+1, inf-1, {X[id], id}, 0);
        else add(X[id]+1, (next(it)->f+X[id])/2, {X[id], id}, 0);
    }
    else{
        if(it == lmao[T[id]].begin())add(1, X[id], {X[id], id}, 1);
        else add((prev(it)->f + X[id])/2+1, X[id], {X[id], id}, 1);
    }
}
 
void s_rmv(set<pair<int, int>>::iterator it, int ty){
    int id = it->s;
    td[id][ty]++;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> K >> q;
    vector<pair<int, pair<int, int>>> ev;
    for(int i = 0; i < n; i++){
        cin >> X[i] >> T[i] >> A[i] >> B[i];
        ev.push_back({A[i], {0, i}});
        ev.push_back({B[i]+1, {1, i}});
    }
    for(int i = 0; i < q; i++){
        cin >> L[i] >> Y[i];
        ev.push_back({Y[i], {2, i}});
        posq.push_back(L[i]);
    }
    sort(posq.begin(), posq.end());
    posq.erase(unique(posq.begin(), posq.end()), posq.end());
    for(auto v: posq)pc[v]++;
    for(int i = 1; i < inf; i++)pc[i]+=pc[i-1];
    sort(ev.begin(), ev.end());
    for(auto v: ev){
        //cout << v.s.f << " " << v.s.s << endl;
        int id = v.s.s;
        if(v.s.f == 0){
            auto it = lmao[T[id]].lower_bound({X[id], id});
            if(it != lmao[T[id]].end())s_rmv(it, 1);
            if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
            it = lmao[T[id]].insert({X[id], id}).f;
            s_add(it, 0);
            s_add(it, 1);
            if(it != lmao[T[id]].begin())s_add(prev(it), 0);
            if(next(it) != lmao[T[id]].end())s_add(next(it), 1);
            tot += (etype[T[id]]++)==0;
        }
        else if(v.s.f == 1){
            auto it = lmao[T[id]].find({X[id], id});
            assert(it != lmao[T[id]].end());
            s_rmv(it, 0);
            s_rmv(it, 1);
            if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
            if(next(it) != lmao[T[id]].end())s_rmv(next(it), 1);
            lmao[T[id]].erase(it);
            it = lmao[T[id]].lower_bound({X[id], id});
            if(it != lmao[T[id]].end())s_add(it, 1);
            if(it != lmao[T[id]].begin())s_add(prev(it), 0);
            tot -= (--etype[T[id]])==0;
        }
        else ans[id] = query(id);
    }
    for(int i = 0; i < q; i++)cout << ans[i] << "\n";
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 480972 KB Output is correct
2 Correct 293 ms 481020 KB Output is correct
3 Correct 301 ms 480880 KB Output is correct
4 Correct 293 ms 480996 KB Output is correct
5 Correct 293 ms 480996 KB Output is correct
6 Correct 300 ms 481280 KB Output is correct
7 Correct 302 ms 481016 KB Output is correct
8 Correct 309 ms 481136 KB Output is correct
9 Correct 310 ms 481228 KB Output is correct
10 Correct 296 ms 481124 KB Output is correct
11 Correct 330 ms 481144 KB Output is correct
12 Correct 310 ms 481020 KB Output is correct
13 Correct 311 ms 481072 KB Output is correct
14 Correct 305 ms 480984 KB Output is correct
15 Correct 295 ms 481100 KB Output is correct
16 Correct 292 ms 481224 KB Output is correct
17 Correct 288 ms 481100 KB Output is correct
18 Correct 290 ms 481184 KB Output is correct
19 Correct 298 ms 481036 KB Output is correct
20 Correct 291 ms 481048 KB Output is correct
21 Correct 292 ms 481180 KB Output is correct
22 Correct 295 ms 481112 KB Output is correct
23 Correct 294 ms 481100 KB Output is correct
24 Correct 306 ms 481072 KB Output is correct
25 Correct 296 ms 481172 KB Output is correct
26 Correct 291 ms 481168 KB Output is correct
27 Correct 295 ms 480972 KB Output is correct
28 Correct 295 ms 481076 KB Output is correct
29 Correct 297 ms 481104 KB Output is correct
30 Correct 291 ms 480972 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 480972 KB Output is correct
2 Correct 293 ms 481020 KB Output is correct
3 Correct 301 ms 480880 KB Output is correct
4 Correct 293 ms 480996 KB Output is correct
5 Correct 293 ms 480996 KB Output is correct
6 Correct 300 ms 481280 KB Output is correct
7 Correct 302 ms 481016 KB Output is correct
8 Correct 309 ms 481136 KB Output is correct
9 Correct 310 ms 481228 KB Output is correct
10 Correct 296 ms 481124 KB Output is correct
11 Correct 330 ms 481144 KB Output is correct
12 Correct 310 ms 481020 KB Output is correct
13 Correct 311 ms 481072 KB Output is correct
14 Correct 305 ms 480984 KB Output is correct
15 Correct 295 ms 481100 KB Output is correct
16 Correct 292 ms 481224 KB Output is correct
17 Correct 288 ms 481100 KB Output is correct
18 Correct 290 ms 481184 KB Output is correct
19 Correct 298 ms 481036 KB Output is correct
20 Correct 291 ms 481048 KB Output is correct
21 Correct 292 ms 481180 KB Output is correct
22 Correct 295 ms 481112 KB Output is correct
23 Correct 294 ms 481100 KB Output is correct
24 Correct 306 ms 481072 KB Output is correct
25 Correct 296 ms 481172 KB Output is correct
26 Correct 291 ms 481168 KB Output is correct
27 Correct 295 ms 480972 KB Output is correct
28 Correct 295 ms 481076 KB Output is correct
29 Correct 297 ms 481104 KB Output is correct
30 Correct 291 ms 480972 KB Output is correct
31 Correct 1180 ms 535876 KB Output is correct
32 Correct 380 ms 488088 KB Output is correct
33 Correct 898 ms 510164 KB Output is correct
34 Correct 1219 ms 535144 KB Output is correct
35 Correct 1159 ms 527132 KB Output is correct
36 Correct 898 ms 509812 KB Output is correct
37 Correct 733 ms 512580 KB Output is correct
38 Correct 642 ms 502584 KB Output is correct
39 Correct 566 ms 504480 KB Output is correct
40 Correct 564 ms 502192 KB Output is correct
41 Correct 881 ms 506284 KB Output is correct
42 Correct 847 ms 513476 KB Output is correct
43 Correct 358 ms 490240 KB Output is correct
44 Correct 853 ms 505864 KB Output is correct
45 Correct 843 ms 501392 KB Output is correct
46 Correct 765 ms 500176 KB Output is correct
47 Correct 501 ms 504856 KB Output is correct
48 Correct 491 ms 503944 KB Output is correct
49 Correct 558 ms 507788 KB Output is correct
50 Correct 577 ms 515268 KB Output is correct
51 Correct 577 ms 505632 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4623 ms 777924 KB Output is correct
2 Correct 3940 ms 620772 KB Output is correct
3 Correct 1958 ms 618256 KB Output is correct
4 Correct 3997 ms 738092 KB Output is correct
5 Correct 2597 ms 550800 KB Output is correct
6 Correct 3366 ms 596504 KB Output is correct
7 Correct 1814 ms 617848 KB Output is correct
8 Correct 3240 ms 728520 KB Output is correct
9 Correct 4333 ms 814984 KB Output is correct
10 Correct 4569 ms 754132 KB Output is correct
11 Correct 1956 ms 645004 KB Output is correct
12 Correct 2685 ms 733544 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5050 ms 794768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 480972 KB Output is correct
2 Correct 293 ms 481020 KB Output is correct
3 Correct 301 ms 480880 KB Output is correct
4 Correct 293 ms 480996 KB Output is correct
5 Correct 293 ms 480996 KB Output is correct
6 Correct 300 ms 481280 KB Output is correct
7 Correct 302 ms 481016 KB Output is correct
8 Correct 309 ms 481136 KB Output is correct
9 Correct 310 ms 481228 KB Output is correct
10 Correct 296 ms 481124 KB Output is correct
11 Correct 330 ms 481144 KB Output is correct
12 Correct 310 ms 481020 KB Output is correct
13 Correct 311 ms 481072 KB Output is correct
14 Correct 305 ms 480984 KB Output is correct
15 Correct 295 ms 481100 KB Output is correct
16 Correct 292 ms 481224 KB Output is correct
17 Correct 288 ms 481100 KB Output is correct
18 Correct 290 ms 481184 KB Output is correct
19 Correct 298 ms 481036 KB Output is correct
20 Correct 291 ms 481048 KB Output is correct
21 Correct 292 ms 481180 KB Output is correct
22 Correct 295 ms 481112 KB Output is correct
23 Correct 294 ms 481100 KB Output is correct
24 Correct 306 ms 481072 KB Output is correct
25 Correct 296 ms 481172 KB Output is correct
26 Correct 291 ms 481168 KB Output is correct
27 Correct 295 ms 480972 KB Output is correct
28 Correct 295 ms 481076 KB Output is correct
29 Correct 297 ms 481104 KB Output is correct
30 Correct 291 ms 480972 KB Output is correct
31 Correct 1180 ms 535876 KB Output is correct
32 Correct 380 ms 488088 KB Output is correct
33 Correct 898 ms 510164 KB Output is correct
34 Correct 1219 ms 535144 KB Output is correct
35 Correct 1159 ms 527132 KB Output is correct
36 Correct 898 ms 509812 KB Output is correct
37 Correct 733 ms 512580 KB Output is correct
38 Correct 642 ms 502584 KB Output is correct
39 Correct 566 ms 504480 KB Output is correct
40 Correct 564 ms 502192 KB Output is correct
41 Correct 881 ms 506284 KB Output is correct
42 Correct 847 ms 513476 KB Output is correct
43 Correct 358 ms 490240 KB Output is correct
44 Correct 853 ms 505864 KB Output is correct
45 Correct 843 ms 501392 KB Output is correct
46 Correct 765 ms 500176 KB Output is correct
47 Correct 501 ms 504856 KB Output is correct
48 Correct 491 ms 503944 KB Output is correct
49 Correct 558 ms 507788 KB Output is correct
50 Correct 577 ms 515268 KB Output is correct
51 Correct 577 ms 505632 KB Output is correct
52 Correct 497 ms 505708 KB Output is correct
53 Correct 498 ms 504640 KB Output is correct
54 Correct 771 ms 529236 KB Output is correct
55 Correct 734 ms 511584 KB Output is correct
56 Correct 684 ms 510756 KB Output is correct
57 Correct 838 ms 512056 KB Output is correct
58 Correct 742 ms 514524 KB Output is correct
59 Correct 695 ms 513584 KB Output is correct
60 Correct 804 ms 515940 KB Output is correct
61 Correct 346 ms 492084 KB Output is correct
62 Correct 497 ms 506520 KB Output is correct
63 Correct 696 ms 519800 KB Output is correct
64 Correct 777 ms 524108 KB Output is correct
65 Correct 963 ms 526388 KB Output is correct
66 Correct 883 ms 512904 KB Output is correct
67 Correct 443 ms 499100 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 480972 KB Output is correct
2 Correct 293 ms 481020 KB Output is correct
3 Correct 301 ms 480880 KB Output is correct
4 Correct 293 ms 480996 KB Output is correct
5 Correct 293 ms 480996 KB Output is correct
6 Correct 300 ms 481280 KB Output is correct
7 Correct 302 ms 481016 KB Output is correct
8 Correct 309 ms 481136 KB Output is correct
9 Correct 310 ms 481228 KB Output is correct
10 Correct 296 ms 481124 KB Output is correct
11 Correct 330 ms 481144 KB Output is correct
12 Correct 310 ms 481020 KB Output is correct
13 Correct 311 ms 481072 KB Output is correct
14 Correct 305 ms 480984 KB Output is correct
15 Correct 295 ms 481100 KB Output is correct
16 Correct 292 ms 481224 KB Output is correct
17 Correct 288 ms 481100 KB Output is correct
18 Correct 290 ms 481184 KB Output is correct
19 Correct 298 ms 481036 KB Output is correct
20 Correct 291 ms 481048 KB Output is correct
21 Correct 292 ms 481180 KB Output is correct
22 Correct 295 ms 481112 KB Output is correct
23 Correct 294 ms 481100 KB Output is correct
24 Correct 306 ms 481072 KB Output is correct
25 Correct 296 ms 481172 KB Output is correct
26 Correct 291 ms 481168 KB Output is correct
27 Correct 295 ms 480972 KB Output is correct
28 Correct 295 ms 481076 KB Output is correct
29 Correct 297 ms 481104 KB Output is correct
30 Correct 291 ms 480972 KB Output is correct
31 Correct 1180 ms 535876 KB Output is correct
32 Correct 380 ms 488088 KB Output is correct
33 Correct 898 ms 510164 KB Output is correct
34 Correct 1219 ms 535144 KB Output is correct
35 Correct 1159 ms 527132 KB Output is correct
36 Correct 898 ms 509812 KB Output is correct
37 Correct 733 ms 512580 KB Output is correct
38 Correct 642 ms 502584 KB Output is correct
39 Correct 566 ms 504480 KB Output is correct
40 Correct 564 ms 502192 KB Output is correct
41 Correct 881 ms 506284 KB Output is correct
42 Correct 847 ms 513476 KB Output is correct
43 Correct 358 ms 490240 KB Output is correct
44 Correct 853 ms 505864 KB Output is correct
45 Correct 843 ms 501392 KB Output is correct
46 Correct 765 ms 500176 KB Output is correct
47 Correct 501 ms 504856 KB Output is correct
48 Correct 491 ms 503944 KB Output is correct
49 Correct 558 ms 507788 KB Output is correct
50 Correct 577 ms 515268 KB Output is correct
51 Correct 577 ms 505632 KB Output is correct
52 Correct 4623 ms 777924 KB Output is correct
53 Correct 3940 ms 620772 KB Output is correct
54 Correct 1958 ms 618256 KB Output is correct
55 Correct 3997 ms 738092 KB Output is correct
56 Correct 2597 ms 550800 KB Output is correct
57 Correct 3366 ms 596504 KB Output is correct
58 Correct 1814 ms 617848 KB Output is correct
59 Correct 3240 ms 728520 KB Output is correct
60 Correct 4333 ms 814984 KB Output is correct
61 Correct 4569 ms 754132 KB Output is correct
62 Correct 1956 ms 645004 KB Output is correct
63 Correct 2685 ms 733544 KB Output is correct
64 Execution timed out 5050 ms 794768 KB Time limit exceeded
65 Halted 0 ms 0 KB -