Submission #109084

#TimeUsernameProblemLanguageResultExecution timeMemory
109084ryanseeNew Home (APIO18_new_home)C++14
57 / 100
5067 ms176832 KiB
#include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define LLINF ((long long) 1e18)//1234567890987654321 #define INF 1234567890ll #define pb push_back #define ins insert #define f first #define s second #define db 0 #define EPS (1e-7) //0.0000001 the value #define PI (acos(-1)) #define MAXN (300006) #define MAXK 26 #define MAXX 15000006 #define ll /*long long*/ int #define ld long double mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) #define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii) #define space " " #define cbr cerr << "hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ((ll)x.size()) #define ph push #define btinpct(x) __builtin_popcountll(x) #define p2(x) (1LL<<(x)) #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi; inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss ll n,k,q,ans[MAXN]; vector<ll>d; struct store { int l, type, a, b, i; } A[MAXN]; vector<store>types[MAXN]; spi Q[MAXN]; // location, time(a,b) with respects to above struct rays { int x=0, in=0, a=0, b=0; // x - point, influence, [a,b] (means inclusive) void close(ll y) { assert(b==-1); b = y; } }; vector<rays>neg,pos; multiset <pi> ms; int currind_pos[MAXN], currind_neg[MAXN]; struct node { int s,e,m; ll v; node *l, *r; node(ll _S, ll _E) { s = _S, e = _E, m = (s+e)/2; v = -INF; if(s!=e) { l = new node(s,m); r = new node(m+1,e); } } void update(ll x, ll y, ll nv) { if(x>y)return; if(s==x&&e==y) { v = max(v, nv); return; } if(x>m) r->update(x,y,nv); else if(y<=m) l->update(x,y,nv); else l->update(x,m,nv), r->update(m+1,y,nv); } ll rmq(ll x) { if(s==e) return v; if(x>m) return max(v,r->rmq(x)); else return max(v,l->rmq(x)); assert(0); } void reset() { v = -INF; if(s==e) return; l->reset(); r->reset(); } } *seg; ll idx(ll x) { return lbd(d,x)-d.begin(); } void solve() { FOR(i,0,n) types[A[i].type].pb(A[i]); FOR(K,1,k+1) { if(types[K].empty()) continue; // sort(all(types[K]), [] (store x, store y) { return x.l < y.l; } ); vector<spi>events; // year to carry out, open/close, index for(auto i : types[K]) events.pb(spi(i.a,pi(0,i.i))), events.pb(spi(i.b,pi(1,i.i))); sort(all(events)); ms.clear(); // insert dummy for neg, as well as ms ms.ins(pi(-INF,n)); ms.ins(pi(INF,n+1)); for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1; for(auto i : events) { ll year = i.f, ind = i.s.s; bool op = i.s.f; ll x = A[ind].l; if(op == 0) { // open auto itr = ms.ins(pi(x,ind)); auto itr2 = next(itr); --itr; // itr -> prev x, itr2 -> next x /* neg rays */ // close ray from next to prev, set end time to (year - 1); // open ray from curr to prev, set start time to (year); // open ray from next to curr, set start time to (year); ll ci = currind_neg[itr2->s]; if(ci == -1) { } else neg[ci].close(year-1); // close ray from next to prev, set end time to (year - 1); currind_neg[ind] = (int)neg.size(); // open ray from curr to prev, set start time to (year); neg.pb({x,x-(x-itr->f)/2,year,-1}); // cerr << ind << ' ' << currind[ind] << '\n'; if(itr2->s < n) { currind_neg[itr2->s] = (int)neg.size(); // open ray from next to curr, set start time to (year); neg.pb({itr2->f, itr2->f-(itr2->f-x)/2,year,-1}); } /* */ /* pos rays */ // close ray from prev to next, set end time to (year-1); // open ray from prev to curr, set start time to (year); // open ray from curr to next, set start time to (year); ci = currind_pos[itr->s]; if(ci == -1) { } else pos[ci].close(year-1); // close ray from prev to next, set end time to (year-1); if(itr->s < n) { currind_pos[itr->s] = (int)pos.size(); pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year); } currind_pos[ind] = (int)pos.size(); pos.pb({x,x+(itr2->f-x)/2,year,-1}); // open ray from curr to next, set start time to (year); /* */ } else { auto itr2 = ms.erase(ms.find(pi(x,ind))); auto itr = prev(itr2); /* neg rays */ // close ray from curr to prev, end time: year // close ray from next to curr, end time: year // open ray from next to prev, start time: year+1 ll ci = currind_neg[ind]; neg[ci].close(year); // close ray from curr to prev, end time: year ci = currind_neg[itr2->s]; if(0)cerr << ci << ' ' << neg.size() << ' ' << itr2->s << '\n'; if(ci == -1) {} else neg[ci].close(year); // close ray from next to curr, end time: year if(itr2->s < n) { currind_neg[itr2->s] = (int)neg.size(); neg.pb({itr2->f, itr2->f-(itr2->f-itr->f)/2,year+1,-1}); // open ray from next to prev, start time: year+1 } /* */ /* pos rays */ // close ray from prev to curr, end time: year // close ray from curr to next, end time: year // open ray from prev to next, start time: year+1 ci = currind_pos[itr->s]; if(ci == -1) { } else pos[ci].close(year); // close ray from prev to curr, end time: year ci = currind_pos[ind]; assert(ci!=-1); pos[ci].close(year); // close ray from curr to next, end time: year if(itr->s < n) { currind_pos[itr->s] = (int)pos.size(); pos.pb({itr->f,itr->f+(itr2->f-itr->f)/2,year+1,-1}); // open ray from prev to next, start time: year+1 } /* */ } } for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0; } for(auto &i : neg) if(i.b == -1) i.b = INF; for(auto &i : pos) if(i.b == -1) i.b = INF; // for(auto &i : neg) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n'; // for(auto &i : pos) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n'; if(0) { FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b); } for(auto i : neg) d.pb(i.a),d.pb(i.b); for(auto i : pos) d.pb(i.a), d.pb(i.b); d.pb(-INF); d.pb(INF); sort(all(d)); d.resize(unique(all(d))-d.begin()); seg=new node(0,siz(d)-1); sort(Q,Q+q); sort(all(neg), [] (rays x, rays y) { return x.in < y.in; }); ll co = 0; FOR(i,0,q) { ll l = Q[i].f, t = Q[i].s.f; ll ind = Q[i].s.s; while(co < neg.size() && neg[co].in <= l) { seg->update(idx(neg[co].a), idx(neg[co].b), neg[co].x); ++co; } ans[ind]=seg->rmq(idx(t))-l; } if(0) seg=new node(0,siz(d)-1); seg->reset(); co = 0; sort(all(pos), [] (rays x, rays y) { return x.in > y.in; }); // reverse(Q,Q+q); for(ll i=q-1;i>=0;--i) { ll l = Q[i].f, t = Q[i].s.f, ind = Q[i].s.s; while(co < pos.size() && pos[co].in >= l) { seg->update(idx(pos[co].a), idx(pos[co].b), -pos[co].x); ++co; } ans[ind]=max(ans[ind],seg->rmq(idx(t))+l); } return; } int main() { FAST cin>>n>>k>>q; FOR(i,0,n) { cin>>A[i].l>>A[i].type>>A[i].a>>A[i].b; A[i].i = i; } FOR(i,0,q) {cin>>Q[i].f>>Q[i].s.f;Q[i].s.s=i;} // FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b); FOR(i,0,q) d.pb(Q[i].s.f); // sort(all(d)); d.resize(unique(all(d))-d.begin()); solve(); // get_neg_rays, & pos_rays; // check for -1 case here i guess: #define storeco currind_pos mmst(storeco,0); sort(Q,Q+q,[](spi x, spi y){return x.s.f < y.s.f; }); sort(A,A+n,[](store x, store y){return x.a<y.a;}); ll co = 0; multiset <pi> ms; multiset <int> deci; FOR(i,1,k+1) deci.ins(0); FOR(i,0,q) { ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s; while(co < n && A[co].a <= t) { ms.ins(pi(A[co].b, A[co].type)); deci.erase(deci.find(storeco[A[co].type])); storeco[A[co].type] ++; deci.ins(storeco[A[co].type]); ++co; } while(ms.size() && ms.begin()->f < t) { deci.erase(deci.find(storeco[ms.begin()->s])); storeco[ms.begin()->s] --; deci.ins(storeco[ms.begin()->s]); ms.erase(ms.begin()); } if(*deci.begin() == 0) ans[ind] = -1; } FOR(i,0,q) cout << ans[i] << '\n'; } /* * 2 1 1 5 1 1 5 4 1 1 4 5 3 */

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:90:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
   ^~~
new_home.cpp:90:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
                                                                  ^~~~~~~~~~~
new_home.cpp:170:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
   ^~~
new_home.cpp:170:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
                                                                 ^~~~~~~~~~~
new_home.cpp:185:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co < neg.size() && neg[co].in <= l) {
         ~~~^~~~~~~~~~~~
new_home.cpp:191:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(0) seg=new node(0,siz(d)-1); seg->reset();
  ^~
new_home.cpp:191:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(0) seg=new node(0,siz(d)-1); seg->reset();
                                  ^~~
new_home.cpp:197:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co < pos.size() && pos[co].in >= l) {
         ~~~^~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:223:6: warning: unused variable 'l' [-Wunused-variable]
   ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
      ^
#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...