oj.uz

Submission #975898

# Submission time Handle Problem Language Result Execution time Memory
975898 2024-05-06T02:42:42 Z boyliguanhan Game (IOI13_game) C++17
100 / 100
 7742 ms 48784 KB 
#include "game.h"
#include<bits/stdc++.h>
#define int long long
#define I signed
int gcd2(int X, int Y) {
    int tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
#define TN 3<<18
namespace TREAP{
    std::mt19937 rng(std::random_device{}());
    int RR,lc[TN],rc[TN],key[TN],ind[TN],C;
    int val[TN],sub[TN];
    int newnode(int v,int i){
        ind[++C]=i;
        key[C]=rng();
        val[C]=sub[C]=v;
        return C;
    }
    void maint(int n){
        sub[n]=gcd2(gcd2(sub[lc[n]],sub[rc[n]]),val[n]);
    }
    int merge(int a,int b){
        if(!a||!b)
            return a+b;
        if(key[a]<key[b]) {
            rc[a]=merge(rc[a],b);
            maint(a); return a;
        }
        lc[b]=merge(a,lc[b]);
        maint(b); return b;
    }
    void split(int a,int p1,int p2,int&x,int&y){
        if(!a) return void(x=y=0);
        if(ind[a]>p1||ind[a]==p1&&val[a]>p2)
            y=a,split(lc[a],p1,p2,x,lc[a]);
        else x=a,split(rc[a],p1,p2,rc[a],y);
        maint(a);
    }
}
namespace SEG{
    int C=0,lc[TN],rc[TN],rt[TN],rtt=0;
    void ins(int &i,int p,int q,int x,int l,int r){
        if(!i) i=++C;
        int A,B,C=TREAP::newnode(x,q);
        TREAP::split(rt[i],q,x,A,B);
        rt[i]=TREAP::merge(A,TREAP::merge(C,B));
        if(l==r) return;
        if(l+r>>1<p)
            ins(rc[i],p,q,x,l+r+2>>1,r);
        else ins(lc[i],p,q,x,l,l+r>>1);
    }
    void del(int i,int p,int q,int x,int l,int r){
        int A,B,C;
        TREAP::split(rt[i],q,x,B,C);
        TREAP::split(B,q,x-1,A,B);
        B=TREAP::merge(TREAP::lc[B],TREAP::rc[B]);
        rt[i]=TREAP::merge(A,TREAP::merge(B,C));
        if(l==r)return;
        if(l+r>>1<p)
            del(rc[i],p,q,x,l+r+2>>1,r);
        else del(lc[i],p,q,x,l,l+r>>1);
    }
    int query(int i,int ll,int rr,int ql,int qr,int l,int r){
        if(!i) return 0;
        if(ll>r||l>rr)
            return 0;
        if(ll<=l&&r<=rr){
            int A,B,C,D;
            TREAP::split(rt[i],qr,1e18,B,C);
            TREAP::split(B,ql,0,A,B);
            D=TREAP::sub[B];
            rt[i]=TREAP::merge(A,TREAP::merge(B,C));
            return D;
        }
        return gcd2(query(lc[i],ll,rr,ql,qr,l,l+r>>1),query(rc[i],ll,rr,ql,qr,l+r+2>>1,r));
    }
}
std::map<int,std::map<int,int>>mp;
void init(I R, I C) {
    TREAP::RR=R;
}
void update(I P, I Q, int K) {
    if(mp[P][Q])
        SEG::del(SEG::rtt,P,Q,mp[P][Q],0,TREAP::RR-1);
    if(K) SEG::ins(SEG::rtt,P,Q,mp[P][Q]=K,0,TREAP::RR-1);
    else mp[P].erase(Q);
}
int calculate(I P, I Q, I U, I V) {
    return SEG::query(SEG::rtt,P,U,Q,V,0,TREAP::RR-1);
}

Compilation message

game.cpp: In function 'void TREAP::split(long long int, long long int, long long int, long long int&, long long int&)':
game.cpp:40:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |         if(ind[a]>p1||ind[a]==p1&&val[a]>p2)
      |                       ~~~~~~~~~~^~~~~~~~~~~
game.cpp: In function 'void SEG::ins(long long int&, long long int, long long int, long long int, long long int, long long int)':
game.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         if(l+r>>1<p)
      |            ~^~
game.cpp:55:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             ins(rc[i],p,q,x,l+r+2>>1,r);
      |                             ~~~^~
game.cpp:56:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         else ins(lc[i],p,q,x,l,l+r>>1);
      |                                ~^~
game.cpp: In function 'void SEG::del(long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         if(l+r>>1<p)
      |            ~^~
game.cpp:66:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             del(rc[i],p,q,x,l+r+2>>1,r);
      |                             ~~~^~
game.cpp:67:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         else del(lc[i],p,q,x,l,l+r>>1);
      |                                ~^~
game.cpp: In function 'long long int SEG::query(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:81:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         return gcd2(query(lc[i],ll,rr,ql,qr,l,l+r>>1),query(rc[i],ll,rr,ql,qr,l+r+2>>1,r));
      |                                               ~^~
game.cpp:81:82: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         return gcd2(query(lc[i],ll,rr,ql,qr,l,l+r>>1),query(rc[i],ll,rr,ql,qr,l+r+2>>1,r));
      |                                                                               ~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 2 ms 4440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 768 ms 18352 KB Output is correct
5 Correct 288 ms 18768 KB Output is correct
6 Correct 1036 ms 15504 KB Output is correct
7 Correct 1244 ms 15360 KB Output is correct
8 Correct 806 ms 7144 KB Output is correct
9 Correct 1193 ms 15732 KB Output is correct
10 Correct 992 ms 15036 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4628 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1230 ms 19664 KB Output is correct
13 Correct 3487 ms 16544 KB Output is correct
14 Correct 560 ms 15508 KB Output is correct
15 Correct 3939 ms 16392 KB Output is correct
16 Correct 289 ms 16536 KB Output is correct
17 Correct 1691 ms 15852 KB Output is correct
18 Correct 2841 ms 17176 KB Output is correct
19 Correct 2439 ms 17000 KB Output is correct
20 Correct 2200 ms 16516 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 757 ms 18308 KB Output is correct
13 Correct 314 ms 18664 KB Output is correct
14 Correct 1035 ms 15304 KB Output is correct
15 Correct 1257 ms 15184 KB Output is correct
16 Correct 779 ms 7120 KB Output is correct
17 Correct 1180 ms 15364 KB Output is correct
18 Correct 989 ms 15376 KB Output is correct
19 Correct 1164 ms 19484 KB Output is correct
20 Correct 3524 ms 16396 KB Output is correct
21 Correct 593 ms 15448 KB Output is correct
22 Correct 3909 ms 16208 KB Output is correct
23 Correct 291 ms 16468 KB Output is correct
24 Correct 1712 ms 15688 KB Output is correct
25 Correct 2877 ms 17040 KB Output is correct
26 Correct 2407 ms 16992 KB Output is correct
27 Correct 2213 ms 16532 KB Output is correct
28 Correct 887 ms 32400 KB Output is correct
29 Correct 1940 ms 35400 KB Output is correct
30 Correct 4777 ms 30100 KB Output is correct
31 Correct 4169 ms 29456 KB Output is correct
32 Correct 851 ms 26552 KB Output is correct
33 Correct 1122 ms 26748 KB Output is correct
34 Correct 346 ms 32576 KB Output is correct
35 Correct 1861 ms 19796 KB Output is correct
36 Correct 3506 ms 32740 KB Output is correct
37 Correct 2796 ms 32988 KB Output is correct
38 Correct 2617 ms 32336 KB Output is correct
39 Correct 2467 ms 22584 KB Output is correct
40 Correct 1 ms 4440 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 775 ms 18916 KB Output is correct
13 Correct 299 ms 18772 KB Output is correct
14 Correct 1031 ms 15644 KB Output is correct
15 Correct 1216 ms 15700 KB Output is correct
16 Correct 762 ms 7532 KB Output is correct
17 Correct 1165 ms 15696 KB Output is correct
18 Correct 986 ms 15044 KB Output is correct
19 Correct 1235 ms 19616 KB Output is correct
20 Correct 3578 ms 16152 KB Output is correct
21 Correct 559 ms 15488 KB Output is correct
22 Correct 3800 ms 16996 KB Output is correct
23 Correct 327 ms 16500 KB Output is correct
24 Correct 1678 ms 16008 KB Output is correct
25 Correct 2859 ms 16956 KB Output is correct
26 Correct 2415 ms 17468 KB Output is correct
27 Correct 2215 ms 16360 KB Output is correct
28 Correct 1016 ms 32492 KB Output is correct
29 Correct 1854 ms 35524 KB Output is correct
30 Correct 4633 ms 30212 KB Output is correct
31 Correct 4338 ms 29528 KB Output is correct
32 Correct 842 ms 26728 KB Output is correct
33 Correct 1090 ms 26960 KB Output is correct
34 Correct 420 ms 32544 KB Output is correct
35 Correct 1894 ms 19708 KB Output is correct
36 Correct 3345 ms 33196 KB Output is correct
37 Correct 2604 ms 33384 KB Output is correct
38 Correct 2462 ms 32532 KB Output is correct
39 Correct 1172 ms 46508 KB Output is correct
40 Correct 2979 ms 48784 KB Output is correct
41 Correct 7742 ms 41664 KB Output is correct
42 Correct 6995 ms 39884 KB Output is correct
43 Correct 601 ms 46668 KB Output is correct
44 Correct 1698 ms 34860 KB Output is correct
45 Correct 2321 ms 22784 KB Output is correct
46 Correct 4811 ms 47412 KB Output is correct
47 Correct 5014 ms 47160 KB Output is correct
48 Correct 4413 ms 46776 KB Output is correct
49 Correct 1 ms 4444 KB Output is correct