Submission #975898

#	Time	Username	Problem	Language	Result	Execution time	Memory
975898		boyliguanhan	Game (IOI13_game)	C++17	100 / 100	7742 ms	48784 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20