QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89968#5249. BanditsGeorge_PloverAC ✓897ms61236kbC++146.1kb2023-03-21 21:30:012023-03-21 21:30:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-21 21:30:03]
  • 评测
  • 测评结果:AC
  • 用时:897ms
  • 内存:61236kb
  • [2023-03-21 21:30:01]
  • 提交

answer

#include <map>
#include <ctime>
#include <array>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110000
#define MOD
#define INF 1000000001
#define vint vector<int>
#define vLL vector<long long>
#define PII pair<int,int>
#define X first
#define Y second
#define LLL __int128_t
#define LL long long
using namespace std;
int n,m;
PII e[MAXN];
vint edge[MAXN];
vint val[MAXN];
array<int,3> que[MAXN];
map<PII,int> Cover;
void BF(int x,int fa,int r,LL d){
    if(d<=r && fa)Cover[{x,fa}]++,Cover[{fa,x}]++;
    int i=0;
    for(auto &v:edge[x]){
        if(v==fa){
            i++;
            continue;
        }
        BF(v,x,r,d+val[x][i++]);
    }
}
struct LCA{
    int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN],top[MAXN];
    LL dis[MAXN];
    LCA(){
        memset(dep,0,sizeof(dep));
        memset(fa,0,sizeof(fa));
        memset(son,0,sizeof(son));
    }
    void dfs1(int x){
        //cout<<"dis"<<x<<" "<<dis[x]<<endl;
        siz[x]=1;
        son[x]=0;
        int i=0;
        for(auto &v:edge[x]){
            if(v==fa[x]){
                i++;
                continue;
            }
            fa[v]=x;
            dep[v]=dep[x]+1;
            dis[v]=dis[x]+val[x][i++];
            dfs1(v);
            siz[x]+=siz[v];
            if(!son[x] || siz[son[x]]<siz[v])
                son[x]=v;
        }
    }
    void dfs2(int x){
        if(x==son[fa[x]]){
            top[x]=top[fa[x]];
        }
        else{
            top[x]=x;
        }
        for(auto &v:edge[x]){
            if(v!=fa[x])
                dfs2(v);
        }
    } 
    inline int lca(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            x=fa[top[x]];
        }
        return dep[x]<dep[y]?x:y;
    }
}lca;

inline LL DIS(int x,int y){
    int c=lca.lca(x,y);
    return lca.dis[x]+lca.dis[y]-2*lca.dis[c];
}
inline int Edis(int x,int y){
    int c=lca.lca(x,y);
    return lca.dep[x]+lca.dep[y]-2*lca.dep[c];
}

struct BIT{
    vint q;
    BIT(){}
    BIT(vint &vec){
        q=vint(vec.size()+1,0);
    }
    void add(int x,int y){
        x++;
        for(int i=x;i<q.size();i+=i&-i)q[i]+=y;
    }
    int sum(int x){
        x++;
        int ret=0;
        for(int i=x;i;i-=i&-i)ret+=q[i];
        return ret;
    }
    int sum(int l,int r){
        if(l>r)return 0;
        return sum(r)-sum(l-1);
    }
    int Ge_sum(int x){
        return sum(x,(int)q.size()-2);
    }
}bit[MAXN],subit[MAXN];

bool vis[MAXN];
int siz[MAXN],max_son[MAXN];
int fa[MAXN],dep[MAXN];
vint cov[MAXN],sub[MAXN];
void Find_root(int x,int fa,vint &vec){
    siz[x]=1;
    max_son[x]=0;
    vec.push_back(x);
    for(auto &v:edge[x]){
        if(!vis[v] && v!=fa){
            Find_root(v,x,vec);
            siz[x]+=siz[v];
            max_son[x]=max(siz[v],max_son[x]);
        }
    }
}
void DivConq(int x,int f){
    vint sub;
    Find_root(x,0,sub);
    int center=0;
    for(auto &i:sub)
        if(max((int)sub.size()-siz[i],max_son[i])*2<=sub.size())
            center=i;
    fa[center]=f;
    dep[center]=dep[f]+1;
    vis[center]=1;
    for(auto &i:edge[center])
        if(!vis[i])
            DivConq(i,center);
}
void Pre_Update(int x,int y){
    for(int i=x,j=0;i;i=fa[i]){
        LL d = DIS(i,x);
        if(y>=d){
            cov[i].push_back(y-d);
            if(j)sub[j].push_back(y-d);
        }
        j=i;
    }
}

void Pre(){
    scanf("%d",&m);
    //m=5;printf("%d\n",m);
    for(int i=1;i<=m;i++){
        char s[3];
        int x,y;
        scanf("%s",s);
        //s[0]=(rand()&1)?'+':'?';putchar(s[0]);putchar(' ');
        if(s[0]=='+'){
            scanf("%d%d",&x,&y);
            //x=rand()%n+1;y=rand()%20;printf("%d %d\n",x,y);
            que[i]={1,x,y};
            Pre_Update(x,y);
        }
        else{
            scanf("%d",&x);
            //x=rand()%(n-1)+1;printf("%d\n",x);
            que[i]={0,e[x].X,e[x].Y};
        }
    }
    for(int i=1;i<=n;i++){
        sort(cov[i].begin(),cov[i].end());
        sort(sub[i].begin(),sub[i].end());
        //cout<<i<<": ";for(auto &j:cov[i])cout<<j<<" ";cout<<endl;
        bit[i]=BIT(cov[i]);
        subit[i]=BIT(sub[i]);
    }
}

inline int get_loc(vint &vec,int v){
    return lower_bound(vec.begin(),vec.end(),v) - vec.begin();
}

void Update(int x,int y){
    for(int i=x,j=0;i;i=fa[i]){
        LL d = DIS(i,x);
        if(y>=d){
            int t = y-d;
            int idx = get_loc(cov[i],t);
            bit[i].add(idx,1);
            if(j){
                idx = get_loc(sub[j],t);
                subit[j].add(idx,1);
            }
        }
        j=i;
    }
}

int Query(int u,int v){
    int ret=0;
    if(dep[u]<dep[v])swap(u,v);
    
    for(int i=u,j=0;i;i=fa[i]){
        int d;
        if(Edis(i,u)<Edis(i,v)){//U
            d = min((LL)INF,DIS(v,i));
        }
        else{//V
            d = min((LL)INF,DIS(u,i));
        }
        int idx = get_loc(cov[i],d);ret+=bit[i].Ge_sum(idx);
        if(j){
            idx = get_loc(sub[j],d);ret-=subit[j].Ge_sum(idx);
        }
        j=i;
    }
    
    return ret;
}

int main(){
    //auto seed = 1679373801;
    //srand(seed);
    //cout<<seed<<endl;
    scanf("%d",&n);
    //n=10;printf("%d\n",n);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        //x=i,y=i+1,z=rand()%10;printf("%d %d %d\n",x,y,z);
        e[i] = {x,y};
        edge[x].push_back(y);val[x].push_back(z);
        edge[y].push_back(x);val[y].push_back(z);
    }
    lca.dfs1(1);
    lca.dfs2(1);
    DivConq(1,0);

    // for(int i=1;i<=n;i++){
    //     printf("fa[%d]=%d",i,fa[i]);
    // }

    Pre();

    for(int i=1;i<=m;i++){
        if(que[i][0]){
            Update(que[i][1],que[i][2]);
            //BF(que[i][1],0,que[i][2],0);
        }
        else{
            printf("%d\n",Query(que[i][1],que[i][2]));
        }
    }



    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 885ms
memory: 58504kb

input:

100000
2670 75097 4080
87477 75802 1712
51835 36626 2883
19412 25923 5852
23976 19312 2520
82536 19514 2492
27160 66601 4483
99087 15088 3504
47050 58820 2964
37063 5696 9901
7717 1496 4891
79136 5448 4340
22575 81285 9289
96280 3803 9877
41980 32139 2855
44236 64938 3298
5983 99947 9666
95856 62545...

output:

0
0
0
2
2
5
2
2
3
4
4
7
8
9
11
10
14
12
12
10
11
10
10
9
10
11
11
9
15
11
14
13
14
16
11
17
15
13
15
14
14
20
15
20
22
22
20
17
23
23
24
29
24
26
30
31
36
28
37
39
35
34
45
39
46
45
43
46
42
49
44
50
43
47
52
50
49
57
51
56
61
58
68
66
69
69
61
63
67
63
72
74
78
72
73
78
77
73
85
76
86
82
85
76
82
8...

result:

ok 50000 lines

Test #2:

score: 0
Accepted
time: 545ms
memory: 47868kb

input:

100000
30038 18547 1594
65857 34063 4575
36600 72585 2328
99199 77595 1590
64257 48199 589
72301 40302 5083
69474 97536 606
60079 67381 9331
65982 39033 205
84122 65285 8508
18167 44905 3704
93490 94986 5941
27155 46374 6616
36232 62969 2212
79807 68652 7199
87352 59101 6880
94571 53224 3552
63610 8...

output:

0
1
3
3
3
3
4
6
10
10
12
14
14
16
18
19
19
19
19
22
22
23
23
23
23
24
25
26
26
26
26
26
26
28
31
31
31
31
31
34
34
36
40
41
41
42
42
42
42
42
44
44
44
47
48
48
48
48
48
48
48
48
48
49
50
50
53
54
54
55
55
56
56
56
56
56
59
62
62
62
62
62
62
62
62
62
62
63
65
67
69
69
69
73
73
73
74
76
76
76
76
76
79...

result:

ok 50000 lines

Test #3:

score: 0
Accepted
time: 319ms
memory: 41448kb

input:

100000
61878 94907 27495452
40498 66053 163324081
9987 91760 269034612
88613 6169 634714395
87422 83687 263182872
22328 64374 595886322
57437 38976 201931120
75020 26926 516189886
88639 96262 269100132
88285 44915 173237252
88407 91931 174315082
12843 50312 641940581
13297 52746 120211351
89089 4638...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 50000 lines

Test #4:

score: 0
Accepted
time: 365ms
memory: 41660kb

input:

100000
45843 69600 747867718
13793 70429 681785830
79985 74443 517803908
38369 67457 257059055
49843 59820 901603712
26439 25214 598556764
10275 5998 613157018
13517 10279 61272074
45577 49749 153772596
30727 68824 827689136
21752 9334 936611496
49173 73121 899562409
67808 9217 665070707
38351 13721...

output:

0
0
0
0
3
0
0
0
0
1
1
0
4
2
0
1
1
0
2
0
3
1
0
0
0
1
1
0
1
2
1
0
0
1
0
1
1
2
2
2
0
0
0
0
2
0
1
1
0
0
3
2
0
0
0
0
0
1
0
1
0
1
0
0
0
2
2
2
0
0
1
0
0
1
1
0
0
0
1
3
2
0
0
0
0
0
0
2
2
0
0
0
0
3
2
3
1
1
0
0
3
1
1
0
2
1
1
2
1
0
1
2
1
0
4
2
1
3
1
1
1
0
0
0
0
1
3
1
1
1
2
1
2
1
0
1
1
0
0
0
2
0
0
0
3
3
1
0
1
1
...

result:

ok 50000 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 20428kb

input:

10
1 6 50
5 7 60
10 7 57
1 7 7
8 10 71
9 8 66
1 3 79
9 4 92
8 2 41
8
? 5
? 2
+ 5 159
? 7
? 4
+ 9 184
? 7
+ 3 291

output:

0
0
1
1
1

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 593ms
memory: 48456kb

input:

100000
34346 47902 18
27392 33766 77
6756 26094 49
22936 48815 19
5650 6237 49
30025 40524 59
54595 38103 73
31226 14746 66
90535 30187 7
31954 7326 41
88688 84625 35
87060 2678 4
51031 33729 53
78866 33403 76
16783 75299 96
96244 52833 50
72746 8315 62
3610 74402 43
5479 75776 55
98976 97524 74
261...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
2
0
0
3
0
1
0
1
0
2
3
0
0
0
0
0
0
1
3
0
1
0
0
1
0
0
1
0
2
2
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
1
0
0
1
2
3
0
0
1
1
2
1
1
2
0
0
1
0
0
3
1
0
0
1
2
1
1
0
1
0
1
1
0
2
0
1
...

result:

ok 50000 lines

Test #7:

score: 0
Accepted
time: 827ms
memory: 54888kb

input:

100000
64148 54183 29
11068 35332 64
25618 18806 90
77040 76732 10
84812 90880 38
42283 75749 18
16322 30644 94
36973 59934 83
29747 75832 83
65108 11462 34
56098 73933 71
13086 78104 88
61180 33475 85
14006 4857 5
3734 96760 71
71250 14549 2
33684 24761 9
14693 12183 86
16730 80793 35
4985 57321 20...

output:

0
0
3
3
3
5
8
10
10
11
12
13
12
13
13
13
14
14
15
16
16
18
17
21
23
22
23
22
22
26
26
33
36
37
36
36
37
36
38
39
41
38
39
42
43
42
42
46
46
46
48
53
49
52
53
54
53
56
58
57
54
59
59
58
58
59
59
55
58
62
58
62
62
60
60
68
68
65
64
70
69
70
72
78
78
76
76
76
77
80
79
80
82
80
84
85
84
86
89
87
83
90
9...

result:

ok 50000 lines

Test #8:

score: 0
Accepted
time: 849ms
memory: 53788kb

input:

100000
14082 229 36
27210 94270 83
4742 68213 50
87953 67081 92
51909 51726 24
90045 60667 69
24283 69653 69
315 54923 19
44878 20782 60
65714 37239 18
18550 90268 99
90511 90267 26
74527 52573 9
44461 37153 92
94712 75548 81
54222 86266 71
99559 95348 72
19824 84320 53
57415 91290 10
1848 64264 73
...

output:

29569
22292
26968
29422
29480
29605
28379
19743
24389
24969
24814
19826
28407
22403
29124
28900
24214
21261
20969
29297
22382
27345
16938
24009
21936
21580
28754
27089
26016
28921
28981
26058
26175
17364
29296
20002
27815
29591
23866
26980
26606
20345
27293
19831
20130
18982
27761
25353
21109
16845
...

result:

ok 50000 lines

Test #9:

score: 0
Accepted
time: 9ms
memory: 20432kb

input:

10
5 9 19
10 7 2
7 8 62
4 6 79
1 4 34
2 10 44
2 3 27
6 3 52
1 9 65
8
+ 7 67
? 2
+ 2 15
? 5
? 5
? 5
+ 9 6
? 9

output:

1
0
0
0
0

result:

ok 5 lines

Test #10:

score: 0
Accepted
time: 426ms
memory: 48292kb

input:

100000
76345 58764 90
38618 20579 17
64447 62815 58
59951 76798 55
74438 62576 95
53180 2222 89
11870 17020 38
39889 48984 74
16333 40563 97
25845 69446 58
5310 92817 62
3253 1870 7
89005 49525 84
82761 65333 77
84354 79477 21
580 24067 88
37079 78987 1
71193 72699 69
74616 30155 89
57080 85169 71
6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
...

result:

ok 50000 lines

Test #11:

score: 0
Accepted
time: 897ms
memory: 61236kb

input:

100000
93170 87268 37
92583 41762 3
93445 95084 53
73369 81234 79
22891 43413 79
16715 69518 7
24171 20852 78
85174 42270 89
66924 67254 49
43354 42747 38
49859 42160 93
40042 50857 22
4048 65749 86
24257 79582 28
87393 44008 99
72905 724 0
91334 97136 21
94537 97499 73
25630 70522 17
60066 15405 10...

output:

0
0
0
0
1
1
1
1
3
4
3
4
4
4
7
7
7
7
7
8
7
9
10
10
10
10
10
14
15
15
17
17
17
17
17
17
19
18
19
23
26
26
24
27
26
29
28
30
30
26
31
35
36
37
38
39
40
41
40
42
40
38
36
42
36
39
40
38
40
50
51
50
54
42
44
56
45
56
59
61
51
63
61
68
62
67
62
69
55
70
68
70
72
72
74
65
66
60
67
74
79
81
67
76
71
90
88
9...

result:

ok 50000 lines

Test #12:

score: 0
Accepted
time: 846ms
memory: 58696kb

input:

100000
19572 74611 8
48607 74319 78
93319 98288 59
52549 90890 45
94797 90913 3
39349 35315 61
38406 98513 80
93016 86528 75
8738 42441 86
30903 41462 74
10393 85631 20
42211 49293 9
94579 14667 32
12354 61859 3
74498 17678 30
73444 85087 70
66415 69027 94
43638 69756 59
39651 46403 85
85460 86047 9...

output:

9967
10077
10052
9942
10077
10159
9742
9523
8936
9982
9997
9033
10148
10124
10094
10155
10003
10077
10088
10116
9958
10208
6409
8007
10173
10046
9956
10078
8473
10167
9797
6675
10136
10067
10098
10107
10033
10138
9480
7747
10040
9954
10013
8801
9980
5539
9953
10077
10072
9992
10040
10153
10134
7920
...

result:

ok 50000 lines

Test #13:

score: 0
Accepted
time: 12ms
memory: 20472kb

input:

10
2 9 4
7 9 90
9 6 18
9 3 17
9 4 36
8 9 4
9 5 11
9 1 99
9 10 75
10
+ 2 5
+ 6 75
? 8
+ 10 14
? 4
? 2
? 4
+ 5 96
? 8
+ 10 53

output:

0
1
0
1
0

result:

ok 5 lines

Test #14:

score: 0
Accepted
time: 187ms
memory: 40380kb

input:

100000
49647 87470 68018
49647 66838 706542
90701 49647 804547
49647 49695 565349
89649 49647 58330
85202 49647 867857
49647 36014 819333
72467 49647 976326
49647 79763 583342
70175 49647 517474
49647 33568 520456
1985 49647 345782
66678 49647 972856
49647 68759 529647
49647 74524 568714
61394 49647...

output:

2
2
3
3
0
0
3
1
7
7
7
0
0
8
6
8
6
4
7
1
6
8
4
7
6
14
5
10
0
4
13
3
14
1
15
7
12
5
3
7
5
15
18
7
4
8
0
3
22
8
5
5
2
16
3
15
6
0
14
5
26
27
3
4
4
28
9
4
0
4
21
5
21
33
3
30
4
14
13
10
14
21
8
36
6
27
38
10
5
32
12
7
0
35
7
7
10
17
10
38
5
2
0
5
5
37
2
45
44
0
44
39
8
4
31
11
2
20
31
10
37
0
0
16
12
1
...

result:

ok 50000 lines

Test #15:

score: 0
Accepted
time: 172ms
memory: 41028kb

input:

100000
89731 79663 351984
79663 48602 135355
79663 1628 661293
37635 79663 426439
42597 79663 617809
80941 79663 434012
79663 55353 351562
70259 79663 728593
56083 79663 465864
79663 49873 535094
79663 82032 99951
79663 72331 884689
4287 79663 744479
53983 79663 394859
79663 11490 97473
23469 79663 ...

output:

1
1
0
5
3
2
5
3
9
4
12
9
8
13
7
7
5
8
16
5
9
14
11
6
9
7
9
9
17
10
18
22
10
20
18
31
8
23
34
23
27
15
10
25
42
12
10
30
12
29
37
22
14
12
15
20
17
21
17
46
50
46
25
13
17
15
25
21
46
33
48
52
15
31
13
54
47
51
41
27
13
17
36
13
17
28
42
13
54
16
55
20
43
52
40
20
19
28
34
60
52
20
41
36
40
48
56
38
...

result:

ok 50000 lines

Test #16:

score: 0
Accepted
time: 180ms
memory: 41292kb

input:

100000
21181 45480 383856
34048 21181 325232
21181 11533 106623
38797 21181 537777
14756 21181 106703
21181 95747 645967
21181 31947 917286
21181 83178 496425
21181 40900 130293
73538 21181 904098
21181 80057 191948
83460 21181 805492
21181 24716 460337
21181 27955 783121
21181 26269 144971
70919 21...

output:

1
1
1
1
3
4
5
7
7
7
7
7
7
10
10
10
10
16
18
18
18
18
19
19
20
20
20
20
20
22
26
26
31
31
34
35
34
34
34
36
36
37
38
39
40
41
43
43
46
46
47
48
49
50
49
53
52
55
55
55
55
55
57
60
58
58
58
62
62
62
61
66
68
67
68
69
68
70
72
73
77
73
76
74
79
78
80
81
81
82
83
84
87
87
89
89
89
89
89
89
91
90
92
94
9...

result:

ok 50000 lines

Test #17:

score: 0
Accepted
time: 4ms
memory: 20428kb

input:

10
10 4 0
7 3 0
10 6 1
5 1 1
5 10 1
8 6 0
10 2 1
1 9 1
1 7 1
10
? 4
+ 6 2
+ 9 0
? 8
+ 8 1
+ 10 0
? 4
+ 4 2
? 5
? 7

output:

0
0
0
2
2

result:

ok 5 lines

Test #18:

score: 0
Accepted
time: 482ms
memory: 45496kb

input:

100000
50403 23870 1
2269 77786 0
88236 65765 0
28248 4408 0
74558 79109 1
75664 73208 1
10792 28375 1
98567 27634 0
90845 81177 0
32096 76545 1
11733 25888 1
68554 31308 0
1066 2492 0
93224 8314 1
69887 89588 1
16083 47361 1
60248 97232 1
86630 50173 0
31340 46107 0
20258 51269 0
39376 44028 0
8841...

output:

0
0
0
0
0
1
0
3
1
3
1
1
1
0
0
0
0
0
1
2
3
5
5
4
9
6
8
0
5
9
0
6
7
7
0
2
7
7
5
10
0
0
0
8
5
7
16
13
2
4
7
3
4
1
1
10
18
2
8
18
1
15
5
13
16
3
11
0
6
13
21
6
0
6
5
16
6
5
1
1
6
24
0
3
20
9
16
4
24
5
14
15
0
0
8
8
11
0
20
10
0
8
7
10
6
8
5
35
2
6
22
1
7
8
3
2
7
4
8
0
8
10
1
13
5
2
4
7
12
36
3
10
2
1
38...

result:

ok 50000 lines

Test #19:

score: 0
Accepted
time: 592ms
memory: 47564kb

input:

100000
49730 265 0
78809 9153 1
65275 81703 0
50422 28990 1
72969 40778 0
21604 34831 0
59452 1530 0
98737 82518 1
37741 5473 1
13736 17478 0
25982 68500 1
86711 84227 0
54130 17469 0
65309 37081 0
35584 46216 1
4853 59899 1
49822 85278 1
8445 72686 0
59147 22165 1
73035 65850 0
16437 25280 0
29017 ...

output:

0
1
1
2
3
4
5
5
10
11
11
12
12
15
16
17
20
21
22
22
22
23
23
24
25
25
26
28
26
28
28
29
29
29
29
31
32
33
34
38
38
38
38
41
41
41
41
43
43
43
44
44
45
45
45
45
45
45
48
48
50
56
56
56
57
57
60
63
63
66
67
68
67
67
67
72
72
72
72
73
73
74
75
77
79
82
82
82
82
83
83
83
84
84
86
87
88
89
89
89
89
89
89...

result:

ok 50000 lines

Test #20:

score: 0
Accepted
time: 521ms
memory: 47776kb

input:

100000
41258 62882 0
64868 74025 1
5722 19530 1
14796 1252 0
2193 72766 0
12881 43335 1
33209 41103 0
35704 53796 0
67373 87901 0
29628 65583 1
30449 73872 0
59461 97707 1
18695 10840 1
92554 59053 1
57943 91567 0
53267 47642 1
41900 45739 0
34663 52104 0
73490 62510 0
31199 75399 1
89391 16176 1
15...

output:

49582
49377
49616
49360
49414
49523
49574
49515
49518
49675
49575
49418
49488
49169
49359
49515
49515
49619
49514
49418
49573
49451
49516
49390
49515
49582
49520
49582
49620
49331
49616
49601
49238
49383
49480
49547
49573
49412
49434
49471
49222
49501
49539
49514
49514
49404
49455
49515
49680
49657
...

result:

ok 50000 lines

Test #21:

score: 0
Accepted
time: 6ms
memory: 20372kb

input:

10
10 2 81
9 6 39
1 6 85
7 9 31
9 3 99
9 5 71
7 8 91
4 9 72
5 10 15
10
+ 8 167
? 5
? 9
+ 3 61
+ 5 239
? 1
+ 3 157
+ 6 247
? 6
? 9

output:

0
0
1
2
2

result:

ok 5 lines

Test #22:

score: 0
Accepted
time: 551ms
memory: 47340kb

input:

100000
33416 72400 76
8810 46018 53
95687 39082 5
54088 16213 60
12596 96485 53
33591 76915 28
86310 6156 80
23776 4482 31
53780 58274 11
16040 62125 13
98537 85883 54
81308 3654 55
30235 20146 96
49716 61880 26
48285 79037 35
8521 48481 15
75112 63257 49
60693 5439 28
66775 33657 69
10262 64007 3
3...

output:

1
5
8
9
10
12
12
12
12
12
12
13
13
13
13
14
14
15
15
19
19
19
20
23
23
24
26
25
25
26
29
30
30
31
32
33
36
38
38
40
40
40
41
42
43
46
46
46
50
51
52
51
52
54
54
54
54
57
56
58
60
60
60
61
62
61
63
64
64
67
67
68
72
72
71
73
74
76
75
79
79
81
81
81
81
83
85
83
81
85
83
86
85
84
86
87
87
89
88
86
92
9...

result:

ok 50000 lines

Test #23:

score: 0
Accepted
time: 541ms
memory: 48160kb

input:

100000
77041 19377 18
97744 17616 36
37860 32974 94
42455 71716 21
27458 30336 73
99486 65469 87
64427 17284 83
28704 96602 34
41036 61624 7
45693 45912 85
51979 49553 95
99543 7021 74
24055 32520 97
12339 70810 57
27835 77595 41
47527 49193 67
35004 99001 31
11 88065 84
42722 19293 81
97216 27174 9...

output:

2
3
6
6
6
6
6
6
6
8
8
8
10
10
10
13
14
16
17
18
19
20
20
20
20
23
24
24
24
26
27
27
27
28
28
28
32
32
34
34
35
35
35
35
35
36
36
36
41
41
41
41
41
41
41
42
42
42
42
42
44
45
45
45
45
47
49
49
49
52
52
53
55
57
60
60
61
61
64
64
66
67
68
69
70
70
70
71
71
75
76
77
82
82
83
83
83
84
84
84
84
85
87
87
...

result:

ok 50000 lines

Test #24:

score: 0
Accepted
time: 528ms
memory: 47404kb

input:

100000
67832 80824 45
57521 11588 3
73893 20303 89
99243 98124 35
28565 32549 48
92669 41118 87
40495 44528 22
78924 44280 6
79988 76789 22
55691 15711 75
91688 75476 11
5712 34840 50
46462 46471 55
77521 45788 51
68055 93814 25
36090 33652 72
78695 16093 48
52374 18265 32
61073 63876 2
99193 69139 ...

output:

49955
49934
49947
49942
49934
49937
49901
49937
49929
49960
49935
49936
49949
49945
49917
49945
49917
49949
49954
49920
49937
49916
49936
49940
49928
49945
49918
49929
49949
49922
49940
49923
49928
49913
49921
49939
49939
49939
49934
49929
49947
49936
49935
49920
49910
49948
49917
49945
49937
49914
...

result:

ok 50000 lines