oj.uz

Submission #975894

# Submission time Handle Problem Language Result Execution time Memory
975894 2024-05-06T02:26:24 Z vjudge1 Game (IOI13_game) C++17
100 / 100
 7869 ms 59672 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 4544 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 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 802 ms 22984 KB Output is correct
5 Correct 295 ms 22608 KB Output is correct
6 Correct 1031 ms 20192 KB Output is correct
7 Correct 1204 ms 19844 KB Output is correct
8 Correct 777 ms 11316 KB Output is correct
9 Correct 1165 ms 20160 KB Output is correct
10 Correct 993 ms 19732 KB Output is correct
11 Correct 1 ms 4440 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 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 0 ms 344 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 4544 KB Output is correct
9 Correct 1 ms 4572 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1193 ms 23776 KB Output is correct
13 Correct 3404 ms 20356 KB Output is correct
14 Correct 564 ms 20196 KB Output is correct
15 Correct 3670 ms 20920 KB Output is correct
16 Correct 385 ms 20692 KB Output is correct
17 Correct 1670 ms 21176 KB Output is correct
18 Correct 2808 ms 22268 KB Output is correct
19 Correct 2395 ms 22316 KB Output is correct
20 Correct 2169 ms 21716 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 4444 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 2 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 773 ms 22780 KB Output is correct
13 Correct 295 ms 22644 KB Output is correct
14 Correct 1030 ms 20264 KB Output is correct
15 Correct 1230 ms 19788 KB Output is correct
16 Correct 784 ms 11216 KB Output is correct
17 Correct 1165 ms 19804 KB Output is correct
18 Correct 998 ms 19540 KB Output is correct
19 Correct 1200 ms 23584 KB Output is correct
20 Correct 3450 ms 20320 KB Output is correct
21 Correct 568 ms 20344 KB Output is correct
22 Correct 3752 ms 20956 KB Output is correct
23 Correct 324 ms 20820 KB Output is correct
24 Correct 1683 ms 20640 KB Output is correct
25 Correct 2797 ms 22176 KB Output is correct
26 Correct 2425 ms 23016 KB Output is correct
27 Correct 2271 ms 21944 KB Output is correct
28 Correct 884 ms 42976 KB Output is correct
29 Correct 1812 ms 45448 KB Output is correct
30 Correct 4698 ms 37008 KB Output is correct
31 Correct 3744 ms 36464 KB Output is correct
32 Correct 844 ms 35976 KB Output is correct
33 Correct 1132 ms 35924 KB Output is correct
34 Correct 361 ms 39236 KB Output is correct
35 Correct 1822 ms 29772 KB Output is correct
36 Correct 3506 ms 43992 KB Output is correct
37 Correct 2596 ms 43676 KB Output is correct
38 Correct 2475 ms 43256 KB Output is correct
39 Correct 2250 ms 32548 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 4696 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 0 ms 444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4544 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 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 782 ms 23116 KB Output is correct
13 Correct 299 ms 22520 KB Output is correct
14 Correct 1037 ms 20048 KB Output is correct
15 Correct 1219 ms 19888 KB Output is correct
16 Correct 766 ms 11176 KB Output is correct
17 Correct 1166 ms 20072 KB Output is correct
18 Correct 973 ms 19528 KB Output is correct
19 Correct 1223 ms 23784 KB Output is correct
20 Correct 3521 ms 20396 KB Output is correct
21 Correct 570 ms 20048 KB Output is correct
22 Correct 3780 ms 20868 KB Output is correct
23 Correct 266 ms 20836 KB Output is correct
24 Correct 1666 ms 20828 KB Output is correct
25 Correct 2812 ms 22264 KB Output is correct
26 Correct 2413 ms 22668 KB Output is correct
27 Correct 2185 ms 22036 KB Output is correct
28 Correct 844 ms 42864 KB Output is correct
29 Correct 1754 ms 45628 KB Output is correct
30 Correct 4561 ms 37028 KB Output is correct
31 Correct 3797 ms 36460 KB Output is correct
32 Correct 840 ms 35824 KB Output is correct
33 Correct 1146 ms 35960 KB Output is correct
34 Correct 400 ms 39248 KB Output is correct
35 Correct 1794 ms 29620 KB Output is correct
36 Correct 3230 ms 43536 KB Output is correct
37 Correct 2575 ms 43924 KB Output is correct
38 Correct 2491 ms 42980 KB Output is correct
39 Correct 1214 ms 57428 KB Output is correct
40 Correct 3114 ms 59672 KB Output is correct
41 Correct 7869 ms 49016 KB Output is correct
42 Correct 6892 ms 47356 KB Output is correct
43 Correct 647 ms 53988 KB Output is correct
44 Correct 1718 ms 44364 KB Output is correct
45 Correct 2187 ms 32644 KB Output is correct
46 Correct 4788 ms 58272 KB Output is correct
47 Correct 4579 ms 58060 KB Output is correct
48 Correct 4464 ms 57700 KB Output is correct
49 Correct 1 ms 4444 KB Output is correct