oj.uz

답안 #1088674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088674 2024-09-14T18:39:11 Z alexander707070 새 집 (APIO18_new_home) C++14
47 / 100
 5000 ms 96164 KB 
#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const int bucket_sz=500,inf=1e9+7;

int n,k,q,x,t,l,r,pt,ans[MAXN];

struct event{
    int x,type,tim,id;

    inline friend bool operator < (event fr,event sc){
        if(fr.tim!=sc.tim)return fr.tim<sc.tim;
        else return fr.type<sc.type;
    }
}s[MAXN];

bool cmp(event fr,event sc){
    return fr.x<sc.x;
}

multiset<int> stores[MAXN];
set< pair<int,int> > ss;
vector< pair<int,int> > st,ts;

vector<event> z,ask;

int sp[MAXN],tim;
vector<int> poss;
priority_queue<int> pq;

int mins(){
    pair<int,int> p=*ss.begin();
    return p.first;
}

int maxs(){
    pair<int,int> p=*ss.rbegin();
    return p.first;
}

int calc(int x,int t){
    if(stores[t].empty())return inf;

    auto it=stores[t].lower_bound(x);

    int p1=-inf,p2=-inf;

    if(it!=stores[t].end())p1=*it;
    if(it!=stores[t].begin()){
        it--; p2=*it;
    }

    return min(abs(x-p1),abs(x-p2));
}

void solve(){

    tim++; ask.clear();
    for(event e:z){
        if(e.type==0 or e.type==2){
            sp[e.id]=tim;
        }else{
            ask.push_back(e);
        }
    }

    poss.clear(); st.clear(); ts.clear();
    for(int i=1;i<=k;i++){
        if(sp[i]==tim)poss.push_back(i);
        else{
            vector<int> w;
            for(int f:stores[i]){
                w.push_back(f);
            }

            if(w.empty()){
                st.push_back({0,inf});
                ts.push_back({inf,2*inf});
                break;
            }

            st.push_back({0,w[0]});
            for(int f=0;f<w.size()-1;f++){
                int pos=(w[f]+w[f+1])/2+(w[f]+w[f+1])%2;
                int val=(w[f+1]-w[f])/2;

                st.push_back({pos,pos+val});
                ts.push_back({pos-(w[f]+w[f+1])%2,val-(pos-(w[f]+w[f+1])%2)});
            }
            ts.push_back({inf,-w.back()});
        }
    }

    if(!st.empty()){
        sort(st.begin(),st.end());
        sort(ts.begin(),ts.end());
        sort(ask.begin(),ask.end(),cmp);

        int pt=0;
        while(!pq.empty())pq.pop();

        for(int i=0;i<ask.size();i++){
            while(pt<st.size() and st[pt].first<=ask[i].x){
                pq.push(st[pt].second);
                pt++;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()-ask[i].x);
        }

        pt=ts.size()-1;
        while(!pq.empty())pq.pop();

        for(int i=ask.size()-1;i>=0;i--){
            while(pt>=0 and ts[pt].first>=ask[i].x){
                pq.push(ts[pt].second);
                pt--;
            }

            ans[ask[i].id]=max(ans[ask[i].id],pq.top()+ask[i].x);
        }
    }

    for(event e:z){
        if(e.type==0){
            stores[e.id].insert(e.x);
        }else if(e.type==2){
            stores[e.id].erase(stores[e.id].find(e.x));
        }else{
            for(int i:poss){
                ans[e.id]=max(ans[e.id],calc(e.x,i));
            }
        }
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        cin>>x>>t>>l>>r;

        pt++; s[pt]={x,0,l,t};
        pt++; s[pt]={x,2,r,t};
    }

    for(int i=1;i<=q;i++){
        cin>>x>>t;

        pt++; s[pt]={x,1,t,i};
    }

    sort(s+1,s+pt+1);

    for(int i=1;i<=pt;i++){
        z.push_back(s[i]);

        if(z.size()==bucket_sz){
            solve(); z.clear();
        }
    }

    if(!z.empty()){
        solve(); z.clear();
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>200000000)cout<<"-1\n";
        else cout<<ans[i]<<"\n";
    }

    return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

*/

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int f=0;f<w.size()-1;f++){
      |                         ~^~~~~~~~~~~
new_home.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i=0;i<ask.size();i++){
      |                     ~^~~~~~~~~~~
new_home.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while(pt<st.size() and st[pt].first<=ask[i].x){
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 18 ms 47452 KB Output is correct
3 Correct 18 ms 47452 KB Output is correct
4 Correct 19 ms 47424 KB Output is correct
5 Correct 19 ms 47448 KB Output is correct
6 Correct 20 ms 47460 KB Output is correct
7 Correct 20 ms 47452 KB Output is correct
8 Correct 21 ms 47388 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 18 ms 47432 KB Output is correct
11 Correct 19 ms 47452 KB Output is correct
12 Correct 19 ms 47452 KB Output is correct
13 Correct 19 ms 47292 KB Output is correct
14 Correct 19 ms 47452 KB Output is correct
15 Correct 22 ms 47452 KB Output is correct
16 Correct 19 ms 47448 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 19 ms 47452 KB Output is correct
19 Correct 21 ms 47452 KB Output is correct
20 Correct 22 ms 47452 KB Output is correct
21 Correct 20 ms 47468 KB Output is correct
22 Correct 21 ms 47448 KB Output is correct
23 Correct 21 ms 47452 KB Output is correct
24 Correct 18 ms 47452 KB Output is correct
25 Correct 18 ms 47452 KB Output is correct
26 Correct 17 ms 47448 KB Output is correct
27 Correct 19 ms 47452 KB Output is correct
28 Correct 18 ms 47452 KB Output is correct
29 Correct 19 ms 47452 KB Output is correct
30 Correct 21 ms 47708 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 18 ms 47452 KB Output is correct
3 Correct 18 ms 47452 KB Output is correct
4 Correct 19 ms 47424 KB Output is correct
5 Correct 19 ms 47448 KB Output is correct
6 Correct 20 ms 47460 KB Output is correct
7 Correct 20 ms 47452 KB Output is correct
8 Correct 21 ms 47388 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 18 ms 47432 KB Output is correct
11 Correct 19 ms 47452 KB Output is correct
12 Correct 19 ms 47452 KB Output is correct
13 Correct 19 ms 47292 KB Output is correct
14 Correct 19 ms 47452 KB Output is correct
15 Correct 22 ms 47452 KB Output is correct
16 Correct 19 ms 47448 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 19 ms 47452 KB Output is correct
19 Correct 21 ms 47452 KB Output is correct
20 Correct 22 ms 47452 KB Output is correct
21 Correct 20 ms 47468 KB Output is correct
22 Correct 21 ms 47448 KB Output is correct
23 Correct 21 ms 47452 KB Output is correct
24 Correct 18 ms 47452 KB Output is correct
25 Correct 18 ms 47452 KB Output is correct
26 Correct 17 ms 47448 KB Output is correct
27 Correct 19 ms 47452 KB Output is correct
28 Correct 18 ms 47452 KB Output is correct
29 Correct 19 ms 47452 KB Output is correct
30 Correct 21 ms 47708 KB Output is correct
31 Correct 2190 ms 56904 KB Output is correct
32 Correct 338 ms 53064 KB Output is correct
33 Correct 144 ms 54612 KB Output is correct
34 Correct 1306 ms 55124 KB Output is correct
35 Correct 899 ms 56840 KB Output is correct
36 Correct 164 ms 56452 KB Output is correct
37 Correct 127 ms 53832 KB Output is correct
38 Correct 84 ms 53864 KB Output is correct
39 Correct 80 ms 53584 KB Output is correct
40 Correct 72 ms 53588 KB Output is correct
41 Correct 206 ms 53840 KB Output is correct
42 Correct 139 ms 53844 KB Output is correct
43 Correct 653 ms 57408 KB Output is correct
44 Correct 175 ms 53584 KB Output is correct
45 Correct 102 ms 53584 KB Output is correct
46 Correct 65 ms 53588 KB Output is correct
47 Correct 62 ms 52816 KB Output is correct
48 Correct 59 ms 52988 KB Output is correct
49 Correct 73 ms 52940 KB Output is correct
50 Correct 158 ms 53180 KB Output is correct
51 Correct 65 ms 53072 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 18 ms 47452 KB Output is correct
3 Correct 18 ms 47452 KB Output is correct
4 Correct 19 ms 47424 KB Output is correct
5 Correct 19 ms 47448 KB Output is correct
6 Correct 20 ms 47460 KB Output is correct
7 Correct 20 ms 47452 KB Output is correct
8 Correct 21 ms 47388 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 18 ms 47432 KB Output is correct
11 Correct 19 ms 47452 KB Output is correct
12 Correct 19 ms 47452 KB Output is correct
13 Correct 19 ms 47292 KB Output is correct
14 Correct 19 ms 47452 KB Output is correct
15 Correct 22 ms 47452 KB Output is correct
16 Correct 19 ms 47448 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 19 ms 47452 KB Output is correct
19 Correct 21 ms 47452 KB Output is correct
20 Correct 22 ms 47452 KB Output is correct
21 Correct 20 ms 47468 KB Output is correct
22 Correct 21 ms 47448 KB Output is correct
23 Correct 21 ms 47452 KB Output is correct
24 Correct 18 ms 47452 KB Output is correct
25 Correct 18 ms 47452 KB Output is correct
26 Correct 17 ms 47448 KB Output is correct
27 Correct 19 ms 47452 KB Output is correct
28 Correct 18 ms 47452 KB Output is correct
29 Correct 19 ms 47452 KB Output is correct
30 Correct 21 ms 47708 KB Output is correct
31 Correct 2190 ms 56904 KB Output is correct
32 Correct 338 ms 53064 KB Output is correct
33 Correct 144 ms 54612 KB Output is correct
34 Correct 1306 ms 55124 KB Output is correct
35 Correct 899 ms 56840 KB Output is correct
36 Correct 164 ms 56452 KB Output is correct
37 Correct 127 ms 53832 KB Output is correct
38 Correct 84 ms 53864 KB Output is correct
39 Correct 80 ms 53584 KB Output is correct
40 Correct 72 ms 53588 KB Output is correct
41 Correct 206 ms 53840 KB Output is correct
42 Correct 139 ms 53844 KB Output is correct
43 Correct 653 ms 57408 KB Output is correct
44 Correct 175 ms 53584 KB Output is correct
45 Correct 102 ms 53584 KB Output is correct
46 Correct 65 ms 53588 KB Output is correct
47 Correct 62 ms 52816 KB Output is correct
48 Correct 59 ms 52988 KB Output is correct
49 Correct 73 ms 52940 KB Output is correct
50 Correct 158 ms 53180 KB Output is correct
51 Correct 65 ms 53072 KB Output is correct
52 Correct 82 ms 57712 KB Output is correct
53 Correct 64 ms 54352 KB Output is correct
54 Correct 102 ms 57516 KB Output is correct
55 Correct 1631 ms 55116 KB Output is correct
56 Correct 2090 ms 55808 KB Output is correct
57 Correct 716 ms 54040 KB Output is correct
58 Correct 1035 ms 54896 KB Output is correct
59 Correct 1267 ms 55500 KB Output is correct
60 Correct 454 ms 53836 KB Output is correct
61 Correct 663 ms 57796 KB Output is correct
62 Correct 722 ms 57800 KB Output is correct
63 Correct 1927 ms 56700 KB Output is correct
64 Correct 2386 ms 56004 KB Output is correct
65 Correct 1309 ms 54352 KB Output is correct
66 Correct 305 ms 53584 KB Output is correct
67 Correct 615 ms 52840 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 47452 KB Output is correct
2 Correct 18 ms 47452 KB Output is correct
3 Correct 18 ms 47452 KB Output is correct
4 Correct 19 ms 47424 KB Output is correct
5 Correct 19 ms 47448 KB Output is correct
6 Correct 20 ms 47460 KB Output is correct
7 Correct 20 ms 47452 KB Output is correct
8 Correct 21 ms 47388 KB Output is correct
9 Correct 21 ms 47452 KB Output is correct
10 Correct 18 ms 47432 KB Output is correct
11 Correct 19 ms 47452 KB Output is correct
12 Correct 19 ms 47452 KB Output is correct
13 Correct 19 ms 47292 KB Output is correct
14 Correct 19 ms 47452 KB Output is correct
15 Correct 22 ms 47452 KB Output is correct
16 Correct 19 ms 47448 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 19 ms 47452 KB Output is correct
19 Correct 21 ms 47452 KB Output is correct
20 Correct 22 ms 47452 KB Output is correct
21 Correct 20 ms 47468 KB Output is correct
22 Correct 21 ms 47448 KB Output is correct
23 Correct 21 ms 47452 KB Output is correct
24 Correct 18 ms 47452 KB Output is correct
25 Correct 18 ms 47452 KB Output is correct
26 Correct 17 ms 47448 KB Output is correct
27 Correct 19 ms 47452 KB Output is correct
28 Correct 18 ms 47452 KB Output is correct
29 Correct 19 ms 47452 KB Output is correct
30 Correct 21 ms 47708 KB Output is correct
31 Correct 2190 ms 56904 KB Output is correct
32 Correct 338 ms 53064 KB Output is correct
33 Correct 144 ms 54612 KB Output is correct
34 Correct 1306 ms 55124 KB Output is correct
35 Correct 899 ms 56840 KB Output is correct
36 Correct 164 ms 56452 KB Output is correct
37 Correct 127 ms 53832 KB Output is correct
38 Correct 84 ms 53864 KB Output is correct
39 Correct 80 ms 53584 KB Output is correct
40 Correct 72 ms 53588 KB Output is correct
41 Correct 206 ms 53840 KB Output is correct
42 Correct 139 ms 53844 KB Output is correct
43 Correct 653 ms 57408 KB Output is correct
44 Correct 175 ms 53584 KB Output is correct
45 Correct 102 ms 53584 KB Output is correct
46 Correct 65 ms 53588 KB Output is correct
47 Correct 62 ms 52816 KB Output is correct
48 Correct 59 ms 52988 KB Output is correct
49 Correct 73 ms 52940 KB Output is correct
50 Correct 158 ms 53180 KB Output is correct
51 Correct 65 ms 53072 KB Output is correct
52 Execution timed out 5101 ms 96164 KB Time limit exceeded
53 Halted 0 ms 0 KB -