Submission #1097695

#TimeUsernameProblemLanguageResultExecution timeMemory
1097695vjudge1Inside information (BOI21_servers)C++11
Compilation error
0 ms0 KiB
#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 = 3e5 + 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*400]; 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); } } }

Compilation message (stderr)

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status