oj.uz

Submission #1088670

# Submission time Handle Problem Language Result Execution time Memory
1088670 2024-09-14T18:36:14 Z alexander707070 New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 58196 KB 
#include<bits/stdc++.h>
#define MAXN 600007
using namespace std;

const int bucket_sz=1,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,last[MAXN];
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]>=inf)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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 11 ms 28504 KB Output is correct
4 Correct 12 ms 28556 KB Output is correct
5 Correct 20 ms 28504 KB Output is correct
6 Correct 22 ms 28720 KB Output is correct
7 Correct 13 ms 28660 KB Output is correct
8 Correct 14 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 31 ms 28504 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 14 ms 28508 KB Output is correct
13 Correct 12 ms 28508 KB Output is correct
14 Correct 12 ms 28508 KB Output is correct
15 Correct 25 ms 28476 KB Output is correct
16 Correct 28 ms 28484 KB Output is correct
17 Correct 19 ms 28716 KB Output is correct
18 Correct 22 ms 28508 KB Output is correct
19 Correct 24 ms 28508 KB Output is correct
20 Correct 23 ms 28508 KB Output is correct
21 Correct 21 ms 28764 KB Output is correct
22 Correct 16 ms 28504 KB Output is correct
23 Correct 28 ms 28732 KB Output is correct
24 Correct 29 ms 28504 KB Output is correct
25 Correct 20 ms 28508 KB Output is correct
26 Correct 17 ms 28508 KB Output is correct
27 Correct 17 ms 28504 KB Output is correct
28 Correct 16 ms 28632 KB Output is correct
29 Correct 12 ms 28656 KB Output is correct
30 Correct 11 ms 28560 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 11 ms 28504 KB Output is correct
4 Correct 12 ms 28556 KB Output is correct
5 Correct 20 ms 28504 KB Output is correct
6 Correct 22 ms 28720 KB Output is correct
7 Correct 13 ms 28660 KB Output is correct
8 Correct 14 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 31 ms 28504 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 14 ms 28508 KB Output is correct
13 Correct 12 ms 28508 KB Output is correct
14 Correct 12 ms 28508 KB Output is correct
15 Correct 25 ms 28476 KB Output is correct
16 Correct 28 ms 28484 KB Output is correct
17 Correct 19 ms 28716 KB Output is correct
18 Correct 22 ms 28508 KB Output is correct
19 Correct 24 ms 28508 KB Output is correct
20 Correct 23 ms 28508 KB Output is correct
21 Correct 21 ms 28764 KB Output is correct
22 Correct 16 ms 28504 KB Output is correct
23 Correct 28 ms 28732 KB Output is correct
24 Correct 29 ms 28504 KB Output is correct
25 Correct 20 ms 28508 KB Output is correct
26 Correct 17 ms 28508 KB Output is correct
27 Correct 17 ms 28504 KB Output is correct
28 Correct 16 ms 28632 KB Output is correct
29 Correct 12 ms 28656 KB Output is correct
30 Correct 11 ms 28560 KB Output is correct
31 Execution timed out 5024 ms 35116 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 58196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 54484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 11 ms 28504 KB Output is correct
4 Correct 12 ms 28556 KB Output is correct
5 Correct 20 ms 28504 KB Output is correct
6 Correct 22 ms 28720 KB Output is correct
7 Correct 13 ms 28660 KB Output is correct
8 Correct 14 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 31 ms 28504 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 14 ms 28508 KB Output is correct
13 Correct 12 ms 28508 KB Output is correct
14 Correct 12 ms 28508 KB Output is correct
15 Correct 25 ms 28476 KB Output is correct
16 Correct 28 ms 28484 KB Output is correct
17 Correct 19 ms 28716 KB Output is correct
18 Correct 22 ms 28508 KB Output is correct
19 Correct 24 ms 28508 KB Output is correct
20 Correct 23 ms 28508 KB Output is correct
21 Correct 21 ms 28764 KB Output is correct
22 Correct 16 ms 28504 KB Output is correct
23 Correct 28 ms 28732 KB Output is correct
24 Correct 29 ms 28504 KB Output is correct
25 Correct 20 ms 28508 KB Output is correct
26 Correct 17 ms 28508 KB Output is correct
27 Correct 17 ms 28504 KB Output is correct
28 Correct 16 ms 28632 KB Output is correct
29 Correct 12 ms 28656 KB Output is correct
30 Correct 11 ms 28560 KB Output is correct
31 Execution timed out 5024 ms 35116 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 11 ms 28504 KB Output is correct
4 Correct 12 ms 28556 KB Output is correct
5 Correct 20 ms 28504 KB Output is correct
6 Correct 22 ms 28720 KB Output is correct
7 Correct 13 ms 28660 KB Output is correct
8 Correct 14 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 31 ms 28504 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 14 ms 28508 KB Output is correct
13 Correct 12 ms 28508 KB Output is correct
14 Correct 12 ms 28508 KB Output is correct
15 Correct 25 ms 28476 KB Output is correct
16 Correct 28 ms 28484 KB Output is correct
17 Correct 19 ms 28716 KB Output is correct
18 Correct 22 ms 28508 KB Output is correct
19 Correct 24 ms 28508 KB Output is correct
20 Correct 23 ms 28508 KB Output is correct
21 Correct 21 ms 28764 KB Output is correct
22 Correct 16 ms 28504 KB Output is correct
23 Correct 28 ms 28732 KB Output is correct
24 Correct 29 ms 28504 KB Output is correct
25 Correct 20 ms 28508 KB Output is correct
26 Correct 17 ms 28508 KB Output is correct
27 Correct 17 ms 28504 KB Output is correct
28 Correct 16 ms 28632 KB Output is correct
29 Correct 12 ms 28656 KB Output is correct
30 Correct 11 ms 28560 KB Output is correct
31 Execution timed out 5024 ms 35116 KB Time limit exceeded
32 Halted 0 ms 0 KB -