Submission #1108433

#TimeUsernameProblemLanguageResultExecution timeMemory
1108433simona1230New Home (APIO18_new_home)C++17
0 / 100
5068 ms48836 KiB
#include <bits/stdc++.h> using namespace std; struct store { int x,t,a,b; store(){} store(int _x,int _t,int _a,int _b) { x=_x; t=_t; a=_a; b=_b; } }; struct hour { int x,t,h,p; hour(){} hour(int _x,int _t,int _h,int _p) { x=_x; t=_t; h=_h; p=_p; } }; int n,q,k; store a[300001]; multiset<int> s[300001]; vector<hour> v; bool cmp(hour h1,hour h2) { if(h1.h==h2.h)return h1.p<h2.p; return h1.h<h2.h; } void read() { cin>>n>>k>>q; for(int i=1;i<=n;i++) { cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b; v.push_back({a[i].x,a[i].t,a[i].a,1}); v.push_back({a[i].x,a[i].t,a[i].b,3}); } for(int i=1;i<=q;i++) { int x,y; cin>>x>>y; v.push_back({x,i,y,2}); } sort(v.begin(),v.end(),cmp); } int ans[300001]; void solve() { for(int i=0;i<v.size();i++) { hour h=v[i]; //cout<<h.x<<" "<<h.t<<" "<<h.p<<" "<<h.h<<endl; if(h.p==1)s[h.t].insert(h.x); else if(h.p==3)s[h.t].erase(s[h.t].find(h.x)); else { int maxx=0; for(int j=1;j<=k;j++) { if(s[j].size()==0) { maxx=-1; break; } else { auto it=s[j].begin(); if(h.x<=*it)maxx=max(maxx,*it-h.x); else { it=s[j].end();it--; if(*it<=h.x)maxx=max(maxx,h.x-*it); else { it=s[j].lower_bound(h.x); maxx=max(maxx,h.x-*it); it++; maxx=max(maxx,*it-h.x); } } } } ans[h.t]=maxx; } } for(int i=1;i<=q;i++) cout<<ans[i]<<endl; } int main() { read(); solve(); 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 (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<hour>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...