Submission #50028

#	Time	Username	Problem	Language	Result	Execution time	Memory
50028		shoemakerjo	Construction of Highway (JOI18_construction)	C++14	100 / 100	664 ms	61716 KiB

construction

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define maxn 100010
#define LEFT 0
#define RIGHT 1
#define pii pair<int, int>
int N;

struct node {
	node *ch[2];
	node *par;
	node *pp; //path pointer

	int sz;
	int val; //store the current value, is passed with path pointer
	int key; //just for debugging purposes, store the index for the node

	node(int vv, int kk) : val(vv), key(kk) { //sets default values
		ch[LEFT] = NULL;
		ch[RIGHT] = NULL;
		pp = NULL;
		par = NULL;
		sz = 1;
	}

	bool isroot() {
		return !par || par->ch[LEFT] != this && par->ch[RIGHT] != this;
	}

	void update() { //really only does update stuff
		sz = 1;
		if (ch[LEFT]) {
			ch[LEFT]->par = this; //why not
			sz += ch[LEFT]->sz;
		}
		if (ch[RIGHT]) {
			ch[RIGHT]->par = this;
			sz += ch[RIGHT]->sz;
		}
	}

	int getDirection() {
		if (par == NULL) return -1;
		if (this == par->ch[LEFT]) return LEFT;
		if (this == par->ch[RIGHT]) return RIGHT;
		return -1;
	}

	void setChild(int dir, node * c) {
		ch[dir] = c;
		if (c) c->par = this;
	}

	void rotateup() {
		int dir = getDirection();
		node *p = par;
		if (!p->isroot()) {
			p->par->ch[p->getDirection()] = this;
		}
		par = p->par;
		node *pMid = ch[!dir];
		p->setChild(dir, pMid);
		setChild(!dir, p);
		pp = p->pp;
		p->pp = NULL;
		val = p->val; 
		p->update();
		update();
	}

};

node *nc[maxn]; //just store some nodes b/c why not
vector<pii> cstuff; //used for counting inversions

void splay(node * x) {
	//all updates for splay should be covered in rotateup()
	x->update();
	while (!x->isroot()) {
		x->update();
		node *p1 = x->par;
		if (!p1->isroot()) {
			node *g = p1->par;
			if (p1->getDirection() == x->getDirection()) {
				p1->rotateup(); //zig zig
			}
			else x->rotateup(); // zig zag

		}
		x->rotateup();
	}

}

void access(node *x) {
	x->update();
	splay(x);
	if (x->ch[RIGHT]) {
		x->ch[RIGHT]->val = x->val;
		x->ch[RIGHT]->pp = x; //cut it off
		x->ch[RIGHT]->par = NULL;
	}
	x->ch[RIGHT] = NULL;
	x->update();
//	cout << "my stuff:  " << x->sz << endl;
	cstuff.push_back(pii(x->val, x->sz));


	while (x->pp) { //not at root of tree of aux trees yet
		node *w = x->pp;
		splay(w);

		if (w->ch[RIGHT]) {
			w->ch[RIGHT]->val = w->val;
			w->ch[RIGHT]->pp = w;
			w->ch[RIGHT]->par = NULL;
		}
		w->ch[RIGHT] = NULL; //temporary for our purposes
		w->update();
		// cout << "key line:   " << w->key << " " << w->val << " " << w->sz << endl;
		cstuff.push_back(pii(w->val, w->sz));
		w->ch[RIGHT] = x;
		x->par = w;
		x->pp = NULL;
		splay(x);
		
	}
}

int seg[maxn*4];
int nums[maxn]; //the number stored for each guy
//set up segment tree stuff
int BIT[maxn];

void update(int spot, int diff) {
	while (spot <= N) {
	//	cout << "u spot:  " << spot << endl;
		BIT[spot] += diff;
		spot += spot & (-spot);
	}
}

int query(int spot) {
	int ans = 0;
	while (spot > 0) {
	//	cout << "spot: " << spot << endl;
		ans += BIT[spot];
		spot -= spot & (-spot);
	}
	return ans;
}

/*
void up(int spot, int diff, int ss, int se, int si) {
	if (spot < ss || spot > se) return;
	if (ss == se) {
		seg[si] += diff;
		return;
	}
	int mid = (ss+se)/2;
	up(spot, diff, ss, mid, si*2+1);
	up(spot, diff, mid+1, se, si*2+2);
	seg[si] = seg[si*2+1] + seg[si*2+2];

}

void update(int spot, int diff) {
	up(spot, diff, 0, N, 0);
}

int qu(int qs, int qe, int ss, int se, int si) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0;
	if (qs <= ss && se <= qe) {
		return seg[si];
	}
	int mid = (ss+se)/2;
	return qu(qs, qe, ss, mid, si*2+1) + 
		qu(qs, qe, mid+1, se, si*2+2);
}

int query(int qs, int qe) {
	return qu(qs, qe, 0, N, 0);
}
*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	set<int> seen;
	map<int, int> encode; //for compression
	//process each edge in order
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
		seen.insert(nums[i]);
	}
	int cv = 0;
	for (int cur : seen) {
		encode[cur] = ++cv; //want 1-indexed
	}
	for (int i = 1; i <= N; i++) {
		nums[i] = encode[nums[i]];
		nc[i] = new node(nums[i], i);
		//cout << "oval:  " << nc[i]->val << endl;
	}
	fill(BIT, BIT+maxn, 0);
	int a, b;
	for (int i = 0; i < N-1; i++) {
		cin >> a >> b; //read in edges in order
		cstuff.clear();
		ll ans = 0LL;
		access(nc[a]); //access this first guy
		//now the things in cstuff should be good to go

		//time to calculate the answer
		//reverse(cstuff.begin(), cstuff.end());
		for (pii cur : cstuff) {
			int curval = cur.first;
			int amount = cur.second;
			// cout << "something on the list: " << curval << " in count of " << amount << endl;
			ans += amount*1LL*query(curval-1); //want amount greater than me
			update(cur.first, cur.second);
		}
		for (pii cur : cstuff) {
			update(cur.first, 0-cur.second);
		}

		nc[b]->pp = nc[a];
		access(nc[b]); //run a classic access now, 
		//				this should augment my value up real nice
		nc[b]->val = nums[b]; //set the thing straight now

		cout << ans << '\n';
	}
	cin >> N;


}
//use ll b/c i think we might need it

Compilation message (stderr)

construction.cpp: In member function 'bool node::isroot()':
construction.cpp:29:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   return !par || par->ch[LEFT] != this && par->ch[RIGHT] != this;
                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'void splay(node*)':
construction.cpp:85:10: warning: unused variable 'g' [-Wunused-variable]
    node *g = p1->par;
          ^

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84