제출 #269875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
269875		theStaticMind	Permutation Recovery (info1cup17_permutation)	C++14	25 / 100	5 ms	384 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

#define rand() (rand() * rand() + rand() + 1)
 
struct Node{
 
	int left, right;
	int key;
	int prior;
	int sum, val, ind, lazy;

	Node(int k = 0){
		left = right = key = prior = sum = val = ind = lazy = 0;
		key = k;
	}

	bool operator<(Node& A){
		return key < A.key;
	}
	bool operator==(Node& A){
		return key == A.key;
	}
 
};
 
vector<Node> node;
 
namespace Treap{
 
	int root = 0;
	int ind = 1;
 
	int new_node(){
		return ind++;
	}

	void push(int j){

		if(!j) return;

		int l = node[j].left;
		int r = node[j].right;

		node[j].key += node[j].lazy;

		if(l){
			node[l].lazy += node[j].lazy;
		}

		if(r){
			node[r].lazy += node[j].lazy;
		}

		node[j].lazy = 0;


	}

	void print(int j){
		if(!j)return;
		push(j);

		int l = node[j].left;
		int r = node[j].right;


		if(l){
			print(l);
		}
		if(r){
			print(r);
		}
	}

	void up(int j){

		if(!j) return;

		int l = node[j].left;
		int r = node[j].right;

		node[j].sum = node[l].sum + node[r].sum + node[j].val;

	}

	void split(int j, Node v, int& l, int& r){

		push(j);

		if(!j) l = r = 0;

		else if(node[j] < v){

			split(node[j].right, v, node[j].right, r);

			l = j;

		}

		else{

			split(node[j].left, v, l, node[j].left);
 
			r = j;
 
		}
		
		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);
 
	}

	void merge(int& j, int l, int r){

		push(l);
		push(r);

		if(!l || !r) j = max(l, r);

		else if(node[l].prior > node[r].prior){

			merge(node[l].right, node[l].right, r);

			j = l;

		} 

		else{

			merge(node[r].left, l, node[r].left);

			j = r;
		}

		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);

	}

	void insert(int& j, int i){

		push(j);

		if(!j) j = i;

		else if(node[i].prior > node[j].prior){

			split(j, node[i], node[i].left, node[i].right);

			j = i;

		}
		else {
			if(node[i] < node[j]) insert(node[j].left, i);
			else insert(node[j].right, i);
		}
 		push(j);
		push(node[j].left);
		push(node[j].right);
		up(j);
 
	}
	
	int erase(int& j, Node v){

		push(j);

		if(node[j] == v) {
			int ret = j;
			merge(j, node[j].left, node[j].right);
			return ret;
		}
		else{
			if(v < node[j]) return erase(node[j].left, v);
			else return erase(node[j].right, v);
		}
		
		push(node[j].left);
		push(node[j].right);
		up(j);

	}

 
	int add(int v, int t, int k){
		int j = new_node();
		node[j].key = v;
		node[j].prior = rand();
		node[j].sum = node[j].val = t;
		node[j].ind = k;
		insert(root, j);
		return j;
	}

	int leftmost(int j){
		if(node[j].left) return leftmost(node[j].left);
		return j;
	}
 
 
	void update(int j, int v){
 		
 		int l = 2, r = j;

 		while(l <= r){
 			int m = (l + r) / 2;
 			int tl, tr;
 			split(root, Node(m), tl, tr);
 			if(node[tl].sum < v - 1){
 				l = m + 1;
 			}
 			else if(node[tl].sum == v - 1){
 				root = tl;
 				add(tr ? node[leftmost(tr)].key : j, v, j);
 				if(tr) node[tr].lazy++;
 				merge(root, root, tr);
 				return;

 			}
 			else r = m - 1;
 			merge(root, tl, tr); 
 		}

 		node[root].lazy++;
 		add(1, v, j);
	}
	
	void dfs(int j){
		push(j);
		int l = node[j].left;
		int r = node[j].right;
		if(l) dfs(l);
		if(r) dfs(r);

		up(j);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;

	node = vector<Node> (n + 1);

	int last = 0;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		Treap::update(i, x - last);
		last = x;

	}

	Treap::dfs(Treap::root);
	for(int i = 1; i <= n; i++) cout << node[i].key << " ";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6