Submission #79799

#TimeUsernameProblemLanguageResultExecution timeMemory
79799aquablitz11trapezoid (balkan11_trapezoid)C++14
95 / 100
585 ms47860 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using piipii = pair<pii, pii>; using pipii = pair<int, pii>; #define all(x) x.begin(), x.end() #define mp make_pair #define F first #define S second pii comb(pii a, pii b) { if (a.F == b.F) return pii(a.F, (a.S+b.S)%30013); else return max(a, b); } const int N = 1<<17; int n; piipii A[N]; struct data { vector<int> key; vector<pii> val; data() { key.clear(); val.clear(); } data(int x) { key.push_back(x); val = vector<pii>(2, pii(0, 0)); } data operator+(data b) { data ret; merge(all(key), all(b.key), back_inserter(ret.key)); ret.val.resize(val.size()+b.val.size()-1, pii(0, 0)); return ret; } } seg[N<<1]; void build(int p=1, int b=0, int e=n-1) { if (b == e) { seg[p] = data(A[b].F.S); return; } int m = (b+e)/2; build(p<<1, b, m); build(p<<1|1, m+1, e); seg[p] = seg[p<<1]+seg[p<<1|1]; } pii query(int x, int y, int p=1, int b=0, int e=n-1) { int l = x, r = n-1; if (b > r || e < l) return pii(0, 0); if (b >= l && e <= r) { int i = lower_bound(all(seg[p].key), y)-seg[p].key.begin()+1; pii ans(0, 0); for (; i <= seg[p].key.size(); i += i&-i) ans = comb(ans, seg[p].val[i]); return ans; } int m = (b+e)/2; pii q1 = query(x, y, p<<1, b, m); pii q2 = query(x, y, p<<1|1, m+1, e); return comb(q1, q2); } inline void updateft(int p, int i, pii v) { for (; i > 0; i -= i&-i) seg[p].val[i] = comb(seg[p].val[i], v); } void update(int x, int y, pii v, int p=1, int b=0, int e=n-1) { if (b > x || e < x) return; updateft(p, lower_bound(all(seg[p].key), y)-seg[p].key.begin()+1, v); if (b == e) return; int m = (b+e)/2; if (x <= m) update(x, y, v, p<<1, b, m); else update(x, y, v, p<<1|1, m+1, e); } int pos(int x) { return lower_bound(A, A+n, mp(mp(x, 0), mp(0, 0)))-A; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d%d%d%d", &A[i].F.F, &A[i].S.F, &A[i].F.S, &A[i].S.S); sort(A, A+n); build(); pii ans(0, 0); for (int i = n-1; i >= 0; --i) { int ul = A[i].F.F, dl = A[i].F.S; int ur = A[i].S.F, dr = A[i].S.S; pii best = query(pos(ur), dr); ++best.F; if (best == pii(1, 0)) best.S = 1; ans = comb(ans, best); update(pos(ul), dl, best); //printf("ul=%d, dl=%d, update to %d %d\n", ul, dl, best.F, best.S); } printf("%d %d\n", ans.F, ans.S); return 0; }

Compilation message (stderr)

trapezoid.cpp: In function 'pii query(int, int, int, int, int)':
trapezoid.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; i <= seg[p].key.size(); i += i&-i)
                ~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &A[i].F.F, &A[i].S.F, &A[i].F.S, &A[i].S.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...