Submission #1371770
Source Code Expand
#define ONLINE_JUDGE #include<bits/stdc++.h> #define HEAP priority_queue #define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i) #define per(i, n) for(int i = (n) - 1; i >= 0 ; --i) #define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i) #define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i) #define FOR(a, b) for(auto (a): (b)) #define mp make_pair #define mt make_tuple #define pb push_back #define X first #define Y second #define eps 1e-6 #define pi 3.1415926535897932384626433832795 #define SZ(x) (int)x.size() #define ALL(x) x.begin(), x.end() #define FILL(a, b) memset((a), (b), sizeof((a))) #define MCPY(a, b) memcpy((a), (b), sizeof((b))) using namespace std; typedef long long LL; typedef double flt; typedef vector<int> vi; typedef vector<LL> vl; typedef pair<int,int> pii; typedef pair<int,LL> pil; typedef pair<LL,int> pli; typedef pair<LL,LL> pll; typedef vector<pil> vil; typedef vector<pii> vii; typedef vector<pli> vli; typedef vector<pll> vll; const int iinf = 1e9 + 7; const int oo = 0x3f3f3f3f; const LL linf = 1ll << 60; const flt dinf = 1e60; template <typename T> inline void scf(T &x) { bool f = 0; x = 0; char c = getchar(); while((c < '0' || c > '9') && c != '-') c = getchar(); if(c == '-') { f = 1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } if(f) x = -x; return; } template <typename T1, typename T2> void scf(T1 &x, T2 &y) { scf(x); return scf(y); } template <typename T1, typename T2, typename T3> void scf(T1 &x, T2 &y, T3 &z) { scf(x); scf(y); return scf(z); } template <typename T1, typename T2, typename T3, typename T4> void scf(T1 &x, T2 &y, T3 &z, T4 &w) { scf(x); scf(y); scf(z); return scf(w); } inline char mygetchar(){ char c = getchar(); while(c == ' ' || c == '\n') c = getchar(); return c; } template <typename T> inline bool chkmax(T &x, const T &y){ return y > x ? x = y, 1 : 0; } template <typename T> inline bool chkmin(T &x, const T &y){ return y < x ? x = y, 1 : 0; } #ifdef ONLINE_JUDGE #define debug(...) ; #else #define debug(...) fprintf(stderr, __VA_ARGS__) #define DEBUG #endif //---------------------------------------------------------head---------------------------------------------------- const int maxn = 3e5 + 100; struct point { int x, y; point(int x = 0, int y = 0): x(x), y(y){} }pnt[maxn]; int M, W, H, n, ans, hsh[maxn], h_n; namespace seg { struct node { node *ch[2]; int num, tag; node(int x = -iinf): num(x){ memset(ch, 0, sizeof ch); tag = 0; } void push() { if(tag) { rep(i, 2) ch[i]->tag += tag, ch[i]->num += tag; tag = 0; } return; } void pull() { num = -iinf; rep(i, 2) chkmax(num, ch[i]->num); return; } }*root; int seg_a, seg_b, seg_q, n; void B(node* &u, int l, int r) { u = new node; if(l == r) { u->num = -hsh[l]; return; } int mid = l + r >> 1; B(u->ch[0], l, mid); B(u->ch[1], mid + 1, r); return u->pull(); } void B(int _n) { root = 0; n = _n; B(root, 0, n - 1); return; } void Q(node* &u, int l, int r) { if(seg_a <= l && r <= seg_b) { chkmax(seg_q, u->num); return; } int mid = l + r >> 1; u->push(); if(seg_a <= mid) Q(u->ch[0], l, mid); if(mid < seg_b) Q(u->ch[1], mid + 1, r); return; } int Q(int l, int r) { if(l > r) return -iinf; seg_a = l, seg_b = r, seg_q = -iinf; Q(root, 0, n - 1); return seg_q; } void M(node* &u, int l, int r) { if(seg_a <= l && r <= seg_b) { u->num += seg_q; u->tag += seg_q; return; } int mid = l + r >> 1; u->push(); if(seg_a <= mid) M(u->ch[0], l, mid); if(mid < seg_b) M(u->ch[1], mid + 1, r); return u->pull(); } void M(int l, int r, int x) { if(l > r) return; debug("M(%d, %d, %d)\n", l, r, x); seg_a = l, seg_b = r, seg_q = x; return M(root, 0, n - 1); } } struct stk { struct item { int x, y, i; item(int x = 0, int y = 0, int i = 0): x(x), y(y), i(i){} }num[maxn]; int n; stk(){ n = 0; } void push(int x, int y) { int i = lower_bound(hsh, hsh + h_n, y) - hsh; debug("push(%d, %d)\t%d\n", x, y, i); if(!n) { num[n++] = item(x, y, i); return; } seg::M(num[n - 1].i, i - 1, x); while(n && num[n - 1].x > x) { --n; seg::M(n ? num[n - 1].i : 0, num[n].i - 1, x - num[n].x); } num[n++] = item(x, y, i); return; } void upd(int i, int x) { int j = n ? num[n - 1].i : 0; seg::M(j, i, x); return; } void undo(int i, int x) { int j = n ? num[n - 1].i : 0; seg::M(j, i, -x); return; } }*A, *B; void work() { M = W >> 1; h_n = 0; sort(pnt, pnt + n, [&](point a, point b){ return a.y < b.y; }); rep(i, n) hsh[h_n++] = pnt[i].y; h_n = unique(hsh, hsh + h_n) - hsh; #ifdef DEBUG rep(i, n) printf("%d %d\n", pnt[i].x, pnt[i].y); debug("%d\n", M); rep(i, h_n) printf("%d ", hsh[i]); putchar('\n'); #endif seg::B(h_n); A = new stk; B = new stk; for(int i = -1, j = 0, y = hsh[j]; j < h_n ; y = hsh[++j]) { debug("===============================================================\n%d\n", y); while(i + 1 < n && pnt[i + 1].y == y) { ++i; if(pnt[i].x <= M) A->push(-pnt[i].x, pnt[i].y); else B->push(pnt[i].x, pnt[i].y); } A->upd(j, 0); B->upd(j, W); chkmax(ans, seg::Q(0, lower_bound(hsh, hsh + h_n, y) - hsh - 1) + ((j == h_n - 1) ? H : hsh[j + 1])); A->undo(j, 0); B->undo(j, W); debug("%d\n", ans); } return; } int main() { scf(W, H, n); rep(i, n){ int x, y; scf(x, y); pnt[i] = point(x, y); } pnt[n++] = point(0, 0); pnt[n++] = point(W, 0); pnt[n++] = point(0, H); pnt[n++] = point(W, H); work(); swap(W, H); rep(i, n) swap(pnt[i].x, pnt[i].y); work(); printf("%d\n", ans << 1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Snuke's Coloring 2 |
User | King_George |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 5952 Byte |
Status | CE |
Compile Error
./Main.cpp:2:9: fatal error: 'bits/stdc++.h' file not found #include<bits/stdc++.h> ^ 1 error generated.