Submission #1097702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097702		vjudge1	Inside information (BOI21_servers)	C++11	100 / 100	331 ms	106324 KiB

servers

#include<bits/stdc++.h>
#define int ll
#define lc (c[rt].l)
#define rc (c[rt].r)
#define mid ((l+r)>>1)
#define rg register
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define prq priority_queue
#define fi first
#define se second
#define DEBUG printf("Debug on line %d\n", __LINE__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 2.4e5 + 5;
const int INF = 0x3f3f3f3f;

inline int read(){
	int n=0, f=1; char ch = getchar();
	for(; !isdigit(ch); ch=getchar()) if(ch == '-') f=-1;
	for(; isdigit(ch); ch=getchar()) n=n*10+ch-'0';
	return n*f;
}

int n, q;
int rt[N];
char opt[N]; int a[N], b[N], ans[N];

namespace dgb_SEG{
	int tp = 0;
	struct node{
		int s;
		int l, r;
	}c[N*300];
	
	void clear(){
		for(int i=1; i<=tp; i++){
			c[i].l = c[i].r = c[i].s = 0;
		}
		tp = 0;
	}
	
	int newnode(){
		++tp;
		c[tp].l = c[tp].r = c[tp].s = 0;
		return tp;
	}
	
	int clone(int x){
		c[++tp] = c[x];
		return tp;
	}
	
	void pushup(int rt){
		c[rt].s = c[lc].s + c[rc].s;
	}
	
	int merge(int x, int y, int l, int r){
		if(!x || !y) return x|y;
		int rt = newnode();
		if(l == r){
			c[rt].s = c[x].s + c[y].s;
			return rt;
		}
		lc = merge(c[x].l, c[y].l, l, mid);
		rc = merge(c[x].r, c[y].r, mid+1, r);
		pushup(rt);
		return rt;
	}
	
	int modify(int rt, int l, int r, int x, int v){
		rt = clone(rt);
		if(l == r){
			c[rt].s += v;
			return rt;
		}
		if(x <= mid) lc = modify(lc, l, mid, x, v);
		else rc = modify(rc, mid+1, r, x, v);
		pushup(rt);
		return rt;
	}
	
	int multiQuery(int rt, int l, int r, int ql, int qr){
		if(!rt || ql>qr || l>qr || r<ql) return 0;
		if(l>=ql && r<=qr) return c[rt].s;
		return multiQuery(lc, l, mid, ql, qr) + multiQuery(rc, mid+1, r, ql, qr);
	}
	
	int singleQuery(int rt, int l, int r, int x){
		if(l == r) return c[rt].s;
		if(x <= mid) return singleQuery(lc, l, mid, x);
		else return singleQuery(rc, mid+1, r, x);
	}
}
/*
6 4
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
*/
signed main(){
//	printf("%lld\n", N);
	n = read(), q = read();
	q += n-1;
	
	for(int i=1; i<=n; i++){
		rt[i] = dgb_SEG::modify(rt[0], 1, n, i, 1);
	}
	
	for(int i=1; i<=q; i++){
		cin >> opt[i];
		if(opt[i] == 'S'){
			a[i] = read(), b[i] = read();
			rt[a[i]] = rt[b[i]] = dgb_SEG::merge(rt[a[i]], rt[b[i]], 1, n);
		} else if(opt[i] == 'Q'){
			a[i] = read(), b[i] = read();
			ans[i] = dgb_SEG::singleQuery(rt[a[i]], 1, n, b[i]);
		} else {
			a[i] = read();
		}
	}
	
	dgb_SEG::clear();
	for(int i=1; i<=n; i++) {
		rt[i] = ++dgb_SEG::tp;
	}
	
	for(int i=q; i>=1; i--){
		if(opt[i] == 'S'){
			rt[a[i]] = dgb_SEG::modify(rt[a[i]], 1, q, i, 1);
			rt[a[i]] = rt[b[i]] = dgb_SEG::merge(rt[a[i]], rt[b[i]], 1, q);
		}
	}
	
//	for(int i=1; i<=q; i++){
//		printf("%lld\n", dgb_SEG::multiQuery(rt[i], 1, q, 1, q)+1);
//	}
	
	for(int i=1; i<=q; i++){
//		printf("%d: ", i);
		if(opt[i] == 'Q'){
			printf(ans[i] ? "yes\n" : "no\n");
		} else if(opt[i] == 'C'){
			printf("%lld\n", dgb_SEG::multiQuery(rt[a[i]], 1, q, 1, i)+1);
		} 
	}
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5