oj.uz

Submission #1097746

# Submission time Handle Problem Language Result Execution time Memory
1097746 2024-10-08T07:01:45 Z vjudge1 Inside information (BOI21_servers) C++14
100 / 100
 546 ms 96084 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
struct node{
    int ls,rs,sum;
}tr[MAXN*400];
int tot=0;
int rt[MAXN],xi[MAXN],yi[MAXN];
char tim[MAXN];
bool ans[MAXN];
void pushup(int x){
    int l=tr[x].ls,r=tr[x].rs;
    tr[x].sum=tr[l].sum+tr[r].sum;
}
int clone(int x){
    tr[++tot]=tr[x];
    return tot;
}
int modify(int x,int l,int r,int pos,int k){
    x=clone(x);
    if(l==r){
        tr[x].sum+=k;
        return x;
    }
    int mid=(l+r)/2;
    if(pos<=mid)tr[x].ls=modify(tr[x].ls,l,mid,pos,k);
    else tr[x].rs=modify(tr[x].rs,mid+1,r,pos,k);
    pushup(x);
    return x;
}
int merge(int x,int y,int l,int r){
    if(!x)return y;
    if(!y)return x;
    int nd=clone(0);
    if(l==r){
        tr[nd].sum=tr[x].sum+tr[y].sum;
        return nd;
    }
    int mid=(l+r)/2;
    tr[nd].ls=merge(tr[x].ls,tr[y].ls,l,mid);
    tr[nd].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
    pushup(nd);
    return nd;
}
int query(int x,int l,int r,int pos){
    if(l==r)return tr[x].sum;
    int mid=(l+r)/2;
    if(pos<=mid)return query(tr[x].ls,l,mid,pos);
    else return query(tr[x].rs,mid+1,r,pos);
}
int qsum(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        return tr[x].sum;
    }
    if(l>r)return 0;
    if(l>R||r<L)return 0;
    if(!x)return 0;
    int mid=(l+r)/2;
    int sum=0;
    sum+=qsum(tr[x].ls,l,mid,L,R);
    sum+=qsum(tr[x].rs,mid+1,r,L,R);
    return sum;
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        rt[i]=modify(rt[0],1,n,i,1);
    }
    for(int i=1;i<=n+m-1;i++){
        char str;
        cin>>str;tim[i]=str;
        if(str=='S'){
            cin>>xi[i]>>yi[i];
            rt[xi[i]]=merge(rt[xi[i]],rt[yi[i]],1,n);
            rt[yi[i]]=rt[xi[i]];
        }else if(str=='Q'){
            cin>>xi[i]>>yi[i];
            ans[i]=query(rt[xi[i]],1,n,yi[i]);
        }else{
            cin>>xi[i];
        }
    }
    for(int i=1;i<=tot;i++)tr[i]={0,0,0};
    tot=0;
    memset(rt,0,sizeof rt);
    for(int i=1;i<=n;i++)rt[i]=modify(rt[0],1,n+m-1,i,0);
    for(int i=n+m-1;i>=1;i--){
        if(tim[i]=='S'){
            rt[xi[i]]=modify(rt[xi[i]],1,n+m-1,i,1);
            rt[xi[i]]=merge(rt[xi[i]],rt[yi[i]],1,n+m-1);
            rt[yi[i]]=rt[xi[i]];
        }
    }

    for(int i=1;i<=n+m-1;i++){
        if(tim[i]=='Q'){
            if(ans[i])cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }else if(tim[i]=='C'){
            cout<<(qsum(rt[xi[i]],1,n+m-1,1,i)+1)<<endl;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3920 KB Output is correct
2 Correct 169 ms 6672 KB Output is correct
3 Correct 171 ms 6992 KB Output is correct
4 Correct 167 ms 6496 KB Output is correct
5 Correct 182 ms 6992 KB Output is correct
6 Correct 179 ms 7112 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3920 KB Output is correct
2 Correct 169 ms 6672 KB Output is correct
3 Correct 171 ms 6992 KB Output is correct
4 Correct 167 ms 6496 KB Output is correct
5 Correct 182 ms 6992 KB Output is correct
6 Correct 179 ms 7112 KB Output is correct
7 Correct 162 ms 3976 KB Output is correct
8 Correct 170 ms 6292 KB Output is correct
9 Correct 177 ms 6740 KB Output is correct
10 Correct 160 ms 6272 KB Output is correct
11 Correct 158 ms 6480 KB Output is correct
12 Correct 162 ms 6920 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3928 KB Output is correct
2 Correct 421 ms 95312 KB Output is correct
3 Correct 433 ms 95128 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3928 KB Output is correct
2 Correct 421 ms 95312 KB Output is correct
3 Correct 433 ms 95128 KB Output is correct
4 Correct 147 ms 3924 KB Output is correct
5 Correct 487 ms 95060 KB Output is correct
6 Correct 420 ms 94036 KB Output is correct
7 Correct 439 ms 94544 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3924 KB Output is correct
2 Correct 425 ms 86096 KB Output is correct
3 Correct 423 ms 86096 KB Output is correct
4 Correct 366 ms 84564 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3924 KB Output is correct
2 Correct 425 ms 86096 KB Output is correct
3 Correct 423 ms 86096 KB Output is correct
4 Correct 366 ms 84564 KB Output is correct
5 Correct 149 ms 3920 KB Output is correct
6 Correct 428 ms 85712 KB Output is correct
7 Correct 364 ms 85196 KB Output is correct
8 Correct 456 ms 85172 KB Output is correct
9 Correct 405 ms 85076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 3920 KB Output is correct
2 Correct 382 ms 95060 KB Output is correct
3 Correct 436 ms 80212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 3920 KB Output is correct
2 Correct 382 ms 95060 KB Output is correct
3 Correct 436 ms 80212 KB Output is correct
4 Correct 148 ms 3920 KB Output is correct
5 Correct 378 ms 94732 KB Output is correct
6 Correct 439 ms 79888 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3896 KB Output is correct
2 Correct 427 ms 86008 KB Output is correct
3 Correct 424 ms 86096 KB Output is correct
4 Correct 385 ms 84576 KB Output is correct
5 Correct 148 ms 3996 KB Output is correct
6 Correct 381 ms 94936 KB Output is correct
7 Correct 435 ms 80208 KB Output is correct
8 Correct 397 ms 72272 KB Output is correct
9 Correct 404 ms 71688 KB Output is correct
10 Correct 459 ms 82920 KB Output is correct
11 Correct 489 ms 82680 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3896 KB Output is correct
2 Correct 427 ms 86008 KB Output is correct
3 Correct 424 ms 86096 KB Output is correct
4 Correct 385 ms 84576 KB Output is correct
5 Correct 148 ms 3996 KB Output is correct
6 Correct 381 ms 94936 KB Output is correct
7 Correct 435 ms 80208 KB Output is correct
8 Correct 397 ms 72272 KB Output is correct
9 Correct 404 ms 71688 KB Output is correct
10 Correct 459 ms 82920 KB Output is correct
11 Correct 489 ms 82680 KB Output is correct
12 Correct 151 ms 3920 KB Output is correct
13 Correct 433 ms 85584 KB Output is correct
14 Correct 372 ms 85072 KB Output is correct
15 Correct 420 ms 85136 KB Output is correct
16 Correct 372 ms 85072 KB Output is correct
17 Correct 145 ms 3932 KB Output is correct
18 Correct 349 ms 94804 KB Output is correct
19 Correct 393 ms 79792 KB Output is correct
20 Correct 379 ms 72136 KB Output is correct
21 Correct 410 ms 71504 KB Output is correct
22 Correct 467 ms 82004 KB Output is correct
23 Correct 546 ms 91692 KB Output is correct
24 Correct 487 ms 89152 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 3920 KB Output is correct
2 Correct 177 ms 6736 KB Output is correct
3 Correct 174 ms 6992 KB Output is correct
4 Correct 178 ms 6484 KB Output is correct
5 Correct 169 ms 6992 KB Output is correct
6 Correct 175 ms 7252 KB Output is correct
7 Correct 150 ms 3924 KB Output is correct
8 Correct 469 ms 95308 KB Output is correct
9 Correct 451 ms 95164 KB Output is correct
10 Correct 146 ms 3920 KB Output is correct
11 Correct 415 ms 86012 KB Output is correct
12 Correct 429 ms 86108 KB Output is correct
13 Correct 355 ms 84592 KB Output is correct
14 Correct 145 ms 4032 KB Output is correct
15 Correct 383 ms 95204 KB Output is correct
16 Correct 422 ms 80200 KB Output is correct
17 Correct 414 ms 72156 KB Output is correct
18 Correct 401 ms 71764 KB Output is correct
19 Correct 467 ms 82624 KB Output is correct
20 Correct 472 ms 82716 KB Output is correct
21 Correct 463 ms 96084 KB Output is correct
22 Correct 505 ms 94888 KB Output is correct
23 Correct 452 ms 85100 KB Output is correct
24 Correct 458 ms 84820 KB Output is correct
25 Correct 450 ms 81520 KB Output is correct
26 Correct 418 ms 72272 KB Output is correct
27 Correct 408 ms 71252 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 168 ms 3920 KB Output is correct
2 Correct 177 ms 6736 KB Output is correct
3 Correct 174 ms 6992 KB Output is correct
4 Correct 178 ms 6484 KB Output is correct
5 Correct 169 ms 6992 KB Output is correct
6 Correct 175 ms 7252 KB Output is correct
7 Correct 150 ms 3924 KB Output is correct
8 Correct 469 ms 95308 KB Output is correct
9 Correct 451 ms 95164 KB Output is correct
10 Correct 146 ms 3920 KB Output is correct
11 Correct 415 ms 86012 KB Output is correct
12 Correct 429 ms 86108 KB Output is correct
13 Correct 355 ms 84592 KB Output is correct
14 Correct 145 ms 4032 KB Output is correct
15 Correct 383 ms 95204 KB Output is correct
16 Correct 422 ms 80200 KB Output is correct
17 Correct 414 ms 72156 KB Output is correct
18 Correct 401 ms 71764 KB Output is correct
19 Correct 467 ms 82624 KB Output is correct
20 Correct 472 ms 82716 KB Output is correct
21 Correct 463 ms 96084 KB Output is correct
22 Correct 505 ms 94888 KB Output is correct
23 Correct 452 ms 85100 KB Output is correct
24 Correct 458 ms 84820 KB Output is correct
25 Correct 450 ms 81520 KB Output is correct
26 Correct 418 ms 72272 KB Output is correct
27 Correct 408 ms 71252 KB Output is correct
28 Correct 146 ms 3924 KB Output is correct
29 Correct 183 ms 6224 KB Output is correct
30 Correct 162 ms 6880 KB Output is correct
31 Correct 163 ms 6376 KB Output is correct
32 Correct 155 ms 6484 KB Output is correct
33 Correct 161 ms 6864 KB Output is correct
34 Correct 145 ms 3924 KB Output is correct
35 Correct 437 ms 95152 KB Output is correct
36 Correct 442 ms 94120 KB Output is correct
37 Correct 423 ms 94548 KB Output is correct
38 Correct 176 ms 3920 KB Output is correct
39 Correct 419 ms 85580 KB Output is correct
40 Correct 369 ms 85128 KB Output is correct
41 Correct 417 ms 85072 KB Output is correct
42 Correct 410 ms 85220 KB Output is correct
43 Correct 159 ms 3956 KB Output is correct
44 Correct 376 ms 94548 KB Output is correct
45 Correct 438 ms 80208 KB Output is correct
46 Correct 384 ms 72224 KB Output is correct
47 Correct 415 ms 71504 KB Output is correct
48 Correct 468 ms 81948 KB Output is correct
49 Correct 512 ms 91728 KB Output is correct
50 Correct 493 ms 89172 KB Output is correct
51 Correct 465 ms 95980 KB Output is correct
52 Correct 448 ms 95252 KB Output is correct
53 Correct 460 ms 94544 KB Output is correct
54 Correct 443 ms 95312 KB Output is correct
55 Correct 419 ms 93780 KB Output is correct
56 Correct 444 ms 84560 KB Output is correct
57 Correct 410 ms 80980 KB Output is correct
58 Correct 430 ms 72272 KB Output is correct
59 Correct 426 ms 71508 KB Output is correct