Submission #1199376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199376		TimDee	Game (IOI13_game)	C++20	80 / 100	3015 ms	162784 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

struct node {
    int l=-1,r=-1;
    ll s=0;
};
struct node2d {
    int root=-1,l=-1,r=-1;
};
int nxt=1, nxt2d=1;

const int sz=1<<30;

const int tsz=1e7;
vector<node> t(tsz);
node2d st[(int)30e4];


ll query(int v, int l, int r, int lx, int rx) {
    if (v==-1) return 0;
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) return t[v].s;
    int m=(l+r)>>1;
    ll lq = query(t[v].l,l,m,lx,rx);
    ll rq = query(t[v].r,m,r,lx,rx);
    return __gcd(lq,rq);
}

ll query2d(int v, int l, int r, int lx, int rx, int ly, int ry) {
    if (v==-1) return 0;
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) {
        return query(st[v].root,0,sz,ly,ry);
    }
    int m=(l+r)>>1;
    ll lq = query2d(st[v].l,l,m,lx,rx,ly,ry);
    ll rq = query2d(st[v].r,m,r,lx,rx,ly,ry);
    return __gcd(lq,rq);
}
ll query2d(int a, int b, int l, int r) {
    return query2d(0,0,sz,a,b,l,r);
}


#define set sett
void set(int v, int l, int r, int i, ll x) {
    if (r-l==1) {
        t[v].s=x;
        return;
    }
    int m=(l+r)>>1;
    if (i<m) {
        if (t[v].l==-1) t[v].l=nxt++;
        set(t[v].l,l,m,i,x);
    } else {
        if (t[v].r==-1) t[v].r=nxt++;
        set(t[v].r,m,r,i,x);
    }
    t[v].s=__gcd( (t[v].l==-1)?0:t[t[v].l].s, (t[v].r==-1)?0:t[t[v].r].s );
}

void set2d(int v, int l, int r, int a, int b, ll x) {
    if (st[v].root==-1) st[v].root=nxt++;
    if (r-l==1) {
        set(st[v].root,0,sz,b,x);
        return;
    }
    int m=(l+r)>>1;
    ll y;
    if (a<m) {
        if (st[v].l==-1) st[v].l=nxt2d++;
        set2d(st[v].l,l,m,a,b,x);
        x=query2d(st[v].l,l,m,l,m,b,b+1);
        y=query2d(st[v].r,m,r,m,r,b,b+1);
    } else {
        if (st[v].r==-1) st[v].r=nxt2d++;
        set2d(st[v].r,m,r,a,b,x);
        x=query2d(st[v].l,l,m,l,m,b,b+1);
        y=query2d(st[v].r,m,r,m,r,b,b+1);
    }
    set(st[v].root,0,sz,b,__gcd(x,y));
}
void set2d(int a, int b, ll x) {
    set2d(0,0,sz,a,b,x);
}


void init(int n, int m) {

}

void update(int p, int q, ll k) {
    set2d(p,q,k);
}
ll calculate(int p, int q, int u, int v) {
    return query2d(p,u+1,q,v+1);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20