oj.uz

Submission #265387

# Submission time Handle Problem Language Result Execution time Memory
265387 2020-08-14T17:42:27 Z rqi Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3167 ms 37248 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<bool> vb; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
constexpr int pct(int x) { return __builtin_popcount(x); } 
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll half(ll x) { return fdiv(x,2); }

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
	// note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi);
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi+1);
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
template<class T> void remDup(vector<T>& v) { 
	sort(all(v)); v.erase(unique(all(v)),end(v)); }

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
template<class A> str ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}
template<class A, class B> str ts(pair<A,B> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

/**
 * Description: Link-Cut Tree. Given a function $f(1\ldots N)\to 1\ldots N,$ 
 	* evaluates $f^b(a)$ for any $a,b.$ \texttt{sz} is for path queries; 
 	* \texttt{sub}, \texttt{vsub} are for subtree queries. \texttt{x->access()} 
 	* brings \texttt{x} to the top and propagates it; its left subtree will be 
 	* the path from \texttt{x} to the root and its right subtree will be empty. 
 	* Then \texttt{sub} will be the number of nodes in the connected component
 	* of \texttt{x} and \texttt{vsub} will be the number of nodes under \texttt{x}.
 	* Use \texttt{makeRoot} for arbitrary path queries.
 * Time: O(\log N)
 * Usage: FOR(i,1,N+1)LCT[i]=new snode(i); link(LCT[1],LCT[2],1);
 * Source: Dhruv Rohatgi, Eric Zhang
	* https://sites.google.com/site/kc97ble/container/splay-tree/splaytree-cpp-3
	* https://codeforces.com/blog/entry/67637
 * Verification: (see README for links)
	* ekzhang Balanced Tokens
	* Dynamic Tree Test (Easy)
	* https://probgate.org/viewproblem.php?pid=578 (The Applicant)
 */

typedef struct snode* sn;
struct snode { //////// VARIABLES
	sn p, c[2]; // parent, children
	bool flip = 0; // subtree flipped or not
	int val, sz; // value in node, # nodes in current splay tree
	int sub, vsub = 0; // vsub stores sum of virtual children
	int vsum;
	snode(int _val) : val(_val) {
		p = c[0] = c[1]; calc(); }
	friend int getSz(sn x) { return x?x->sz:0; }
	friend int getSub(sn x) { return x?x->sub:0; }
	friend int getVsum(sn x) { return x?x->vsum:0; }
	void prop() { // lazy prop
		if (!flip) return;
		swap(c[0],c[1]); flip = 0;
		F0R(i,2) if (c[i]) c[i]->flip ^= 1;
	}
	void calc() { // recalc vals
		F0R(i,2) if (c[i]) c[i]->prop();
		sz = 1+getSz(c[0])+getSz(c[1]);
		sub = 1+getSub(c[0])+getSub(c[1])+vsub;
		vsum = val+getVsum(c[0])+getVsum(c[1]);
	}
	//////// SPLAY TREE OPERATIONS
	int dir() {
		if (!p) return -2;
		F0R(i,2) if (p->c[i] == this) return i;
		return -1; // p is path-parent pointer
	} // -> not in current splay tree
	// test if root of current splay tree
	bool isRoot() { return dir() < 0; } 
	friend void setLink(sn x, sn y, int d) {
		if (y) y->p = x;
		if (d >= 0) x->c[d] = y; }
	void rot() { // assume p and p->p propagated
		assert(!isRoot()); int x = dir(); sn pa = p;
		setLink(pa->p, this, pa->dir());
		setLink(pa, c[x^1], x); setLink(this, pa, x^1);
		pa->calc(); calc();
	}
	void splay() {
		while (!isRoot() && !p->isRoot()) {
			p->p->prop(), p->prop(), prop();
			dir() == p->dir() ? p->rot() : rot();
			rot();
		}
		if (!isRoot()) p->prop(), prop(), rot();
		prop();
	}
	sn fbo(int b) { // find by order
		prop(); int z = getSz(c[0]); // of splay tree
		if (b == z) { splay(); return this; }
		return b < z ? c[0]->fbo(b) : c[1] -> fbo(b-z-1);
	}
	//////// BASE OPERATIONS
	void access() { // bring this to top of tree, propagate
		for (sn v = this, pre = NULL; v; v = v->p) {
			v->splay(); // now switch virtual children
			if (pre) v->vsub -= pre->sub;
			if (v->c[1]) v->vsub += v->c[1]->sub;
			v->c[1] = pre; v->calc(); pre = v;
		}
		splay(); assert(!c[1]); // right subtree is empty
	}
	void makeRoot() { 
		access(); flip ^= 1; access(); assert(!c[0] && !c[1]); }
	//////// QUERIES
	friend sn lca(sn x, sn y) {
		if (x == y) return x;
		x->access(), y->access(); if (!x->p) return NULL;
		x->splay(); return x->p?:x; // y was below x in latter case
	} // access at y did not affect x -> not connected
	friend bool connected(sn x, sn y) { return lca(x,y); } 
	// # nodes above
	int distRoot() { access(); return getSz(c[0]); } 
	sn getRoot() { // get root of LCT component
		access(); sn a = this; 
		while (a->c[0]) a = a->c[0], a->prop();
		a->access(); return a;
	}
	sn getPar(int b) { // get b-th parent on path to root
		access(); b = getSz(c[0])-b; assert(b >= 0);
		return fbo(b);
	} // can also get min, max on path to root, etc
	//////// MODIFICATIONS
	void set(int v) { access(); val = v; calc(); } 
	friend void link(sn x, sn y, bool force = 0) { 
		assert(!connected(x,y)); 
		if (force) y->makeRoot(); // make x par of y
		else { y->access(); assert(!y->c[0]); }
		x->access(); setLink(y,x,0); y->calc();
	}
	friend void cut(sn y) { // cut y from its parent
		y->access(); assert(y->c[0]);
		y->c[0]->p = NULL; y->c[0] = NULL; y->calc(); }
	friend void cut(sn x, sn y) { // if x, y adj in tree
		x->makeRoot(); y->access(); 
		assert(y->c[0] == x && !x->c[0] && !x->c[1]); cut(y); }
};
sn LCT[400005];

const int mx = 150005;
int N, L;
int X[mx];
int par[mx];
set<pi> m;
int M;

void init(int _N, int _L, int _X[])
{
	N = _N;
	L = _L;
	M = N+5;
	for(int i = 0; i < N; i++){
		X[i] = _X[i];
		m.ins(mp(X[i], i));
	}
	X[N] = 2*MOD;
	m.ins(mp(2*MOD, N));
	LCT[N] = new snode(0);

	for(int i = 0; i < N; i++){
		LCT[i] = new snode(0);
		LCT[i+M] = new snode(0);
		link(LCT[i+M], LCT[i], 1);
		//dbg(i+M, i);
	}
	//dbg(N, M);
	for(int i = 0; i < N; i++){
		int to = (m.lb(mp(X[i]+L+1, 0)))->s;
		int nex = (next(m.find(mp(X[i], i))))->s;
		//dbg(i, to, nex);
		if(nex != N && (m.lb(mp(X[nex]+L+1, 0)))->s == to){
			LCT[i+M]->set(0);
			link(LCT[nex], LCT[i+M], 1);
			par[i] = nex;
			//dbg(nex, i+M);
		}
		else{
			LCT[i+M]->set(1);
			link(LCT[to], LCT[i+M], 1);
			par[i] = to;
			//dbg(to, i+M);
		}
	}
	
}

int spec;

void upd(int i){
	if(i == -1) return;
	//dbg(i);
	// for(int i = 0; i < N; i++){
	// 	dbg(i, par[i]);
	// }
	// dbg(i+M, par[i]);
	// dbg(connected(LCT[i+M], LCT[par[i]]));	
	// dbg(i+M, par[i]);

	if(spec != i) cut(LCT[i+M], LCT[par[i]]);
	//dbg("cut", i+M, par[i]);

	int to = (m.lb(mp(X[i]+L+1, 0)))->s;
	int nex = (next(m.find(mp(X[i], i))))->s;
	//dbg(to, nex);

	if(nex != N && (m.lb(mp(X[nex]+L+1, 0)))->s == to){
		LCT[i+M]->set(0);
		//dbg(nex, i+M);
		link(LCT[nex], LCT[i+M], 1);
		
		par[i] = nex;
	}
	else{
		LCT[i+M]->set(1);
		//dbg(to, i+M);
		link(LCT[to], LCT[i+M], 1);
		
		par[i] = to;
	}
}

int update(int i, int y)
{
	spec = i;
	//dbg(i, y);
	//erase from lct
	int prv1 = -1, prv2 = -1;

	if(m.find(mp(X[i], i)) != m.begin()){
		prv1 = (prev(m.find(mp(X[i], i))))->s;
	}
	auto it = m.lb(mp(X[i]-L, 0));
	if(it != m.begin()){
		prv2 = prev(it)->s;
	}
	//dbg(prv1, prv2);
	m.erase(mp(X[i], i));
	cut(LCT[i+M], LCT[par[i]]);
	upd(prv1);
	upd(prv2);

	X[i] = y;
	//add to lct
	m.ins(mp(X[i], i));
	prv1 = -1, prv2 = -1;
	if(m.find(mp(X[i], i)) != m.begin()){
		prv1 = (prev(m.find(mp(X[i], i))))->s;
	}
	it = m.lb(mp(X[i]-L, 0));
	if(it != m.begin()){
		prv2 = prev(it)->s;
	}
	
	//dbg(prv1, prv2, i);
	upd(prv1);
	upd(prv2);
	upd(i);

	LCT[N]->makeRoot();
	int beg = (m.begin())->s;
	LCT[beg]->access();
	int ans = getVsum(LCT[beg]);

	return ans;
}

Compilation message

elephants.cpp: In function 'void setIn(str)':
elephants.cpp:169:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  169 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void setOut(str)':
elephants.cpp:170:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  170 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In constructor 'snode::snode(int)':
elephants.cpp:208:17: warning: '*<unknown>.snode::c[1]' is used uninitialized in this function [-Wuninitialized]
  208 |   p = c[0] = c[1]; calc(); }
      |              ~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 242 ms 4352 KB Output is correct
8 Correct 252 ms 5496 KB Output is correct
9 Correct 491 ms 12664 KB Output is correct
10 Correct 278 ms 12376 KB Output is correct
11 Correct 259 ms 12152 KB Output is correct
12 Correct 841 ms 12520 KB Output is correct
13 Correct 293 ms 12152 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 242 ms 4352 KB Output is correct
8 Correct 252 ms 5496 KB Output is correct
9 Correct 491 ms 12664 KB Output is correct
10 Correct 278 ms 12376 KB Output is correct
11 Correct 259 ms 12152 KB Output is correct
12 Correct 841 ms 12520 KB Output is correct
13 Correct 293 ms 12152 KB Output is correct
14 Correct 503 ms 6392 KB Output is correct
15 Correct 536 ms 7416 KB Output is correct
16 Correct 1173 ms 13048 KB Output is correct
17 Correct 1192 ms 17272 KB Output is correct
18 Correct 1326 ms 17272 KB Output is correct
19 Correct 353 ms 17272 KB Output is correct
20 Correct 1214 ms 17144 KB Output is correct
21 Correct 1217 ms 17144 KB Output is correct
22 Correct 423 ms 16808 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 242 ms 4352 KB Output is correct
8 Correct 252 ms 5496 KB Output is correct
9 Correct 491 ms 12664 KB Output is correct
10 Correct 278 ms 12376 KB Output is correct
11 Correct 259 ms 12152 KB Output is correct
12 Correct 841 ms 12520 KB Output is correct
13 Correct 293 ms 12152 KB Output is correct
14 Correct 503 ms 6392 KB Output is correct
15 Correct 536 ms 7416 KB Output is correct
16 Correct 1173 ms 13048 KB Output is correct
17 Correct 1192 ms 17272 KB Output is correct
18 Correct 1326 ms 17272 KB Output is correct
19 Correct 353 ms 17272 KB Output is correct
20 Correct 1214 ms 17144 KB Output is correct
21 Correct 1217 ms 17144 KB Output is correct
22 Correct 423 ms 16808 KB Output is correct
23 Correct 2033 ms 37248 KB Output is correct
24 Correct 1995 ms 37240 KB Output is correct
25 Correct 1646 ms 37240 KB Output is correct
26 Correct 877 ms 37240 KB Output is correct
27 Correct 851 ms 36984 KB Output is correct
28 Correct 1640 ms 6008 KB Output is correct
29 Correct 1642 ms 6008 KB Output is correct
30 Correct 1633 ms 6008 KB Output is correct
31 Correct 1654 ms 6008 KB Output is correct
32 Correct 844 ms 36728 KB Output is correct
33 Correct 756 ms 35912 KB Output is correct
34 Correct 864 ms 36856 KB Output is correct
35 Correct 812 ms 37240 KB Output is correct
36 Correct 1402 ms 36600 KB Output is correct
37 Correct 2359 ms 36988 KB Output is correct
38 Correct 948 ms 35832 KB Output is correct
39 Correct 837 ms 36856 KB Output is correct
40 Correct 947 ms 35832 KB Output is correct
41 Correct 3167 ms 36604 KB Output is correct
42 Correct 2989 ms 36776 KB Output is correct