Submission #687845

#	Time	Username	Problem	Language	Result	Execution time	Memory
687845		lam	Game (IOI13_game)	C++14	0 / 100	1 ms	496 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define ll long long
using namespace std;

typedef pair<int,int> ii;
#define ff first
#define ss second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int inf = 1e9 + 7;
int n,m;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node
{
    node *l=nullptr, *r=nullptr;
    int wt; ll val;
    ii key;
    node (ii _key, ll x)
    {
        key=_key; val=x;
        wt=rng(); l=r=0;
    }
};

struct Node
{
    Node *l=nullptr, *r=nullptr;
    node *it=nullptr;
    Node() {}
};

Node *tree = nullptr;

inline ll get_g(node *&x)
{
    return (x)?x->val:0LL;
}

void upd(node *&x)
{
    x->val = gcd2(x->val,gcd2(get_g(x->l),get_g(x->r)));
}

pair<node*, node*> split(node *x, ii key)
{
    if (!x) return {nullptr,nullptr};
    if (x->key<=key) {pair<node*,node*> tt=split(x->r,key); x->r=tt.ff; upd(x); return{x,tt.ss}; }
    else {pair<node*,node*> tt=split(x->l,key); x->l=tt.ss; upd(x); return {tt.ff,x}; }
}

node* merg(node *l, node *r)
{
    if (!l||!r) return (!l)?r:l;
    if (l->wt>r->wt){
        l->r=merg(l->r,r); upd(l); return l;
    }
    else {
        r->l=merg(l,r->l); upd(r); return r;
    }
}

void ins(node *&x, ii key, ll val)
{
    auto [a,b] = split(x,make_pair(key.ff,key.ss-1));
    auto [c,d] = split(b,key);
    x = merg(a,merg(new node(key,val),d));
}

ll get2(node *&x, int l, int r)
{
    if (!x) return 0LL;
    auto [a,b] = split(x,make_pair(l-1,inf));
    auto [c,d] = split(b,make_pair(r,inf));
    ll ans = c->val;
    x = merg(a,merg(c,d));
    return ans;
}

void updat(Node *&x, int lx, int rx, int idx, int idy, ll val)
{
    if (!x) x=new Node();
    ins(x->it,{idy,idx},val);
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (idx<=mid) updat(x->l,lx,mid,idx,idy,val);
    else updat(x->r,mid+1,rx,idx,idy,val);
}

ll get(Node *&x, int lx, int rx, int l, int r, int ly, int ry)
{
    if (!x) return 0LL;
    if (lx>r||rx<l) return 0LL;
    if (lx>=l&&rx<=r) return get2(x->it,ly,ry);
    int mid=(lx+rx)/2;
    return gcd2(get(x->l,lx,mid,l,r,ly,ry),get(x->r,mid+1,rx,l,r,ly,ry));
}

void init(int R, int C) {
    n=R; m=C;
}

void update(int P, int Q, long long K) {
    P++; Q++;
    updat(tree,1,n,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return get(tree,1,n,P,U,Q,V);
}

Compilation message (stderr)

game.cpp: In function 'void ins(node*&, ii, long long int)':
game.cpp:74:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     auto [a,b] = split(x,make_pair(key.ff,key.ss-1));
      |          ^
game.cpp:75:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     auto [c,d] = split(b,key);
      |          ^
game.cpp: In function 'long long int get2(node*&, int, int)':
game.cpp:82:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     auto [a,b] = split(x,make_pair(l-1,inf));
      |          ^
game.cpp:83:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     auto [c,d] = split(b,make_pair(r,inf));
      |          ^

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