Submission #925161

#TimeUsernameProblemLanguageResultExecution timeMemory
925161idiotcomputertrapezoid (balkan11_trapezoid)C++11
100 / 100
171 ms63384 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define pii pair<ll,ll> #define f first #define s second #define FOR(i, a,b) for(i = a; i < b; i++) #define ROF(i, b,a) for(i = b-1; i >= a; i--) const int mxN = 4*1e5; int n; ll mod = 30013; pii stree[4*mxN+1][2]; pii comp(pii a, pii b){ if (a.f == b.f){ return {a.f, (a.s+b.s)%mod}; } else { if (a.f < b.f){ return b; } return a; } } void upd(int t, pii v, bool w, int l = 0, int r = 4*n-1, int idx = 0){ if (l > t || r < t){ return; } if (l == r){ stree[idx][w] = v; return; } int m = (l+r)/2; upd(t,v,w,l,m,2*idx+1); upd(t,v,w,m+1,r,2*idx+2); stree[idx][w] = comp(stree[2*idx+1][w],stree[2*idx+2][w]); return; } pii query(int tl, int tr, bool w, int l = 0, int r = 4*n-1, int idx = 0){ if (l > tr || r < tl){ return {0,0}; } if (l >= tl && r <= tr){ /* if (tr == 18){ cout << l << "-" << r << " " << stree[idx][w].f << "," << stree[idx][w].s << '\n'; }*/ return stree[idx][w]; } int m = (l+r)/2; return comp(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2)); } bool c2(pii &a, pii &b){ return a.f < b.f; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int i,j; FOR (i,0,4*mxN+1){ stree[i][0] = {0,0}; stree[i][1] = {0,0}; } cin >> n; vector<pii> p(4*n); int vals[n][4]; FOR(i,0,n){ cin >> p[4*i].f >> p[4*i+1].f >> p[4*i+2].f >> p[4*i+3].f; } FOR (i,0,4*n) p[i].s = i; sort(p.begin(),p.end(),c2); int nv = 0; int last; FOR(i,0,4*n){ last = p[i].f; // cout << i << "," << last << " "; FOR(j,i,4*n){ if (p[j].f == last){ vals[p[j].s/4][p[j].s%4] = nv; p[j].f = nv; } else { break; } } i = j-1; nv++; } // cout << '\n'; pii res[n]; FOR (i,0,n) res[i] = {1,1}; int cnt[n][2]; memset(cnt,0,sizeof(cnt)); int idx; pii temp; FOR (i,0,4*n){ idx = p[i].s / 4; //cout << idx << " " << p[i].f << ' ' << p[i].s << '\n'; if (cnt[idx][0] == 0 && cnt[idx][1] == 0){ if (p[i].s%4 < 2){ temp = query(0,vals[idx][2],1); // cout << temp.f << "," << temp.s << '\n'; res[idx] = comp(res[idx],{temp.f+1,temp.s}); } else { temp = query(0,vals[idx][0],0); // cout << temp.f << "," << temp.s << '\n'; res[idx] = comp(res[idx],{temp.f+1,temp.s}); } } if (p[i].s%4 < 2){ cnt[idx][0]++; if (cnt[idx][0] == 2){ // cout << res[idx].f << "\n"; upd(vals[idx][3],res[idx],1); } } else { cnt[idx][1]++; if (cnt[idx][1] == 2){ //cout << res[idx].f << '\n'; upd(vals[idx][1],res[idx],0); } } } // FOR (i,0,n) cout << vals[i][0] << "," << vals[i][1] << "," << vals[i][2] << "," << vals[i][3] << '\n'; pii tot = {0,0}; FOR (i,0,n){ // cout << res[i].f << ',' << res[i].s << '\n'; tot = comp(tot, res[i]); } cout << tot.f << " " << tot.s << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...