Submission #397713

#TimeUsernameProblemLanguageResultExecution timeMemory
397713jeroenodbDancing Elephants (IOI11_elephants)C++14
0 / 100
9078 ms332 KiB
#include "bits/stdc++.h" #include "elephants.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1e9; template<class T> struct splaytree { #define l kid(b) #define r kid(b^1) #define L kid(0) #define R kid(1) struct node { T val; node *c[2] = {NULL,NULL}, *par =NULL; bool flip=false,pathtop=true; node(const T& v) : val(v) {} node*& kid(bool k) {return c[k^flip];} node() {} }; static void push(node* at) { if(at->flip) { if(at->L) at->L->flip^=1; if(at->R) at->R->flip^=1; swap(at->L,at->R); at->flip=0; } } static void recalc(node* at) { at->val.recalc(); if(at->L) at->val.recalc(at->L->val); if(at->R) at->val.recalc(at->R->val); } static void print(node* n) { if(n==NULL) return; print(n->L); cout << n->val << ' '; print(n->R); } static void rotate(node* n) { // Precondition: n is not the root, Postcondition: rotates n to the place of its parent // assert(n and !n->pathtop and n->par); node* par = n->par; push(par); push(n); if(!par->pathtop) { auto gp = par->par; if(gp->L==par) gp->L=n; else if(gp->R==par) gp->R=n; } n->par = par->par; bool b= n!=par->L; par->l = n->r; // Fix right child of current node if(n->r) n->r->par = par; n->r = par; // Put parent under current node par->par = n; swap(par->pathtop, n->pathtop); recalc(par); recalc(n); } static void splay(node* n) { while(!n->pathtop) { if(n->par->pathtop) { rotate(n); } else { auto p = n->par, gp = p->par; // Double rotations if((p->L==n) == (gp->L==p)) { rotate(p); } else { rotate(n); } rotate(n); } } push(n); } #undef l #undef r #undef L #undef R }; struct vertex{ int sm=0, id; bool white=false; vertex(int idd, bool b){id=idd, white = b, sm=!b;} vertex(){} void recalc(const vertex& o) { sm += o.sm; } void recalc() { sm = !white; } }; ostream& operator<<(ostream& c, const vertex& v) { return c << v.id << (v.white?"W ":"B "); } struct linkcut { // initially the linkcut tree consists of n disconnected size 1 trees. typedef splaytree<vertex> bst; typedef bst::node node; int n=0; node* t=NULL; linkcut() {} linkcut(int N) { n=N; t = new node[n+1]; // for(int i=0;i<n;++i) { // t[i] = node(vertex()); // } } void add(int i, bool white) { int id = i; if(i>=n and i<2*n) i-=n; t[i] = node(vertex(id,white)); } node* expose(int u) { node *at = NULL, *par = t+u; for(;par; at=par,par = par->par) { bst::splay(par); if(par->kid(1)) { par->kid(1)->pathtop = true; par->kid(1) = NULL; } if(at) at->pathtop = false; par->kid(1) = at; bst::recalc(par); } bst::splay(t+u); return t+u; } void reroot(int u) { node* root = expose(u); root->flip^=1; } void link(int u, int v) { reroot(u); t[u].par = t+v; // connect with unmarked edge } void cut(int u, int v) { reroot(u); expose(v); node* at = t+v; assert(at->kid(0) == t+u); if(at->kid(0)) { auto& prev = at->kid(0); prev->par=NULL; prev->pathtop = true; prev = NULL; } bst::recalc(at); } ll calc(int u, int v) { reroot(u); auto root = expose(v); // bst::print(root); return root->val.sm; } }; int n,l; map<pi,int> m; linkcut lc; vi xs; void init(int N, int L, int X[]) { l=L; lc = linkcut(N*2+2); n = N; xs = vi(X,X+n); lc.add(n*2,true), lc.add(n*2+1,true); for(int i=0;i<n;++i) { int x = X[i]; m[{x,i}] = i; m[{x+L,i+n}]= i+n; lc.add(i,false), lc.add(i+n,true); lc.link(i,i+n); } m[{-2*oo,n*2}] = n*2; m[{oo*2,n*2}] = n*2+1; for(int i=0;i<n;++i) { auto iter = m.lower_bound({X[i]+L+1,-1}); lc.link(i+n,iter->second); } auto iter = m.lower_bound({-2*oo+L+1,-1}); lc.link(n*2,iter->second); } int update(int i, int y) { int X = xs[i]; // white node -> cut lc.cut(i+n,m.upper_bound({X+l+1,-1})->second); auto fix = [](int x, int j) { auto iter = m.find({x,j}); auto maybe = --m.lower_bound({x,-1}); m.erase(iter); if(maybe->second>=n) { // node is white and thus connected lc.cut(j, maybe->second); lc.link(maybe->second, next(maybe)->second); } }; fix(X+l,i+n); fix(X,i); xs[i] = y; // debug(xs); auto fix2 = [](int x, int j) { auto iter = m.lower_bound({x,-1}); auto maybe = prev(iter); if(maybe->second>=n) { // node is white and thus connected lc.cut(maybe->second, next(maybe)->second); lc.link(maybe->second, j); } m[{x,j}] = j; }; auto iter = m.lower_bound({y+l+1,-1}); lc.link(i+n,iter->second); fix2(y+l,i+n); fix2(y,i); return lc.calc(n*2,n*2+1); }
#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...