답안 #1097694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097694	2024-10-08T03:16:22 Z	vjudge1	Inside information (BOI21_servers)	C++11	컴파일 오류	0 ms	0 KB

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 = 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

servers.cpp: In function 'll dgb_SEG::merge(ll, ll, ll, ll)':
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:68:33: note: in expansion of macro 'mid'
   68 |   lc = merge(c[x].l, c[y].l, l, mid);
      |                                 ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:69:30: note: in expansion of macro 'mid'
   69 |   rc = merge(c[x].r, c[y].r, mid+1, r);
      |                              ^~~
servers.cpp: In function 'll dgb_SEG::modify(ll, ll, ll, ll, ll)':
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:80:11: note: in expansion of macro 'mid'
   80 |   if(x <= mid) lc = modify(lc, l, mid, x, v);
      |           ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:80:35: note: in expansion of macro 'mid'
   80 |   if(x <= mid) lc = modify(lc, l, mid, x, v);
      |                                   ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:81:24: note: in expansion of macro 'mid'
   81 |   else rc = modify(rc, mid+1, r, x, v);
      |                        ^~~
servers.cpp: In function 'll dgb_SEG::multiQuery(ll, ll, ll, ll, ll)':
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:89:28: note: in expansion of macro 'mid'
   89 |   return multiQuery(lc, l, mid, ql, qr) + multiQuery(rc, mid+1, r, ql, qr);
      |                            ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:89:58: note: in expansion of macro 'mid'
   89 |   return multiQuery(lc, l, mid, ql, qr) + multiQuery(rc, mid+1, r, ql, qr);
      |                                                          ^~~
servers.cpp: In function 'll dgb_SEG::singleQuery(ll, ll, ll, ll)':
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:94:11: note: in expansion of macro 'mid'
   94 |   if(x <= mid) return singleQuery(lc, l, mid, x);
      |           ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:94:42: note: in expansion of macro 'mid'
   94 |   if(x <= mid) return singleQuery(lc, l, mid, x);
      |                                          ^~~
servers.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    5 | #define mid (l+r>>1)
      |              ~^~
servers.cpp:95:31: note: in expansion of macro 'mid'
   95 |   else return singleQuery(rc, mid+1, r, x);
      |                               ^~~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status