oj.uz

Submission #687860

# Submission time Handle Problem Language Result Execution time Memory
687860 2023-01-27T03:05:19 Z lam Game (IOI13_game) C++17
100 / 100
 7060 ms 67580 KB 
#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=0LL, vval=0LL;
    ii key;
    node (ii _key, ll x)
    {
        key=_key; val=x;
        vval=x;
        wt=rng()%INT_MAX;
    }
};

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)
{
    if (!x) return;
    x->val = gcd2(x->vval,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)
{
//    cout<<key.ff<<' '<<key.ss<<" = "<<val<<'\n';
    auto [a,b] = split(x,make_pair(key.ff,key.ss-1));
    auto [c,d] = split(b,key);
    x = merg(merg(a,(new node(key,val))),d);
}

ll get2(node *&x, int l, int r)
{
    auto [a,b] = split(x,make_pair(l-1,inf));
    auto [c,d] = split(b,make_pair(r,inf));
    ll ans = get_g(c);
//    cout<<ans<<'\n';
    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();
//    cout<<lx<<' '<<rx<<" + ";
    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)
    {
//        cout<<l<<' '<<r<<' '<<ly<<' '<<ry<<": ";
        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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 737 ms 11384 KB Output is correct
5 Correct 321 ms 11212 KB Output is correct
6 Correct 977 ms 8816 KB Output is correct
7 Correct 1113 ms 8400 KB Output is correct
8 Correct 741 ms 7568 KB Output is correct
9 Correct 1064 ms 8648 KB Output is correct
10 Correct 857 ms 8120 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1240 ms 15368 KB Output is correct
13 Correct 3321 ms 11828 KB Output is correct
14 Correct 521 ms 12876 KB Output is correct
15 Correct 3518 ms 13044 KB Output is correct
16 Correct 280 ms 12868 KB Output is correct
17 Correct 1533 ms 10172 KB Output is correct
18 Correct 2708 ms 14292 KB Output is correct
19 Correct 2256 ms 14396 KB Output is correct
20 Correct 2078 ms 13844 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 738 ms 11436 KB Output is correct
13 Correct 343 ms 11212 KB Output is correct
14 Correct 950 ms 8728 KB Output is correct
15 Correct 1101 ms 8560 KB Output is correct
16 Correct 728 ms 7504 KB Output is correct
17 Correct 1060 ms 8532 KB Output is correct
18 Correct 887 ms 8208 KB Output is correct
19 Correct 1211 ms 15444 KB Output is correct
20 Correct 3263 ms 11800 KB Output is correct
21 Correct 544 ms 12980 KB Output is correct
22 Correct 3598 ms 13136 KB Output is correct
23 Correct 369 ms 12740 KB Output is correct
24 Correct 1547 ms 10088 KB Output is correct
25 Correct 2817 ms 14296 KB Output is correct
26 Correct 2280 ms 14364 KB Output is correct
27 Correct 2045 ms 13896 KB Output is correct
28 Correct 863 ms 36428 KB Output is correct
29 Correct 1736 ms 38936 KB Output is correct
30 Correct 4525 ms 30216 KB Output is correct
31 Correct 4065 ms 29796 KB Output is correct
32 Correct 747 ms 29560 KB Output is correct
33 Correct 1103 ms 29504 KB Output is correct
34 Correct 379 ms 32692 KB Output is correct
35 Correct 1749 ms 23944 KB Output is correct
36 Correct 3439 ms 36860 KB Output is correct
37 Correct 2733 ms 37084 KB Output is correct
38 Correct 2572 ms 36352 KB Output is correct
39 Correct 2218 ms 30848 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 737 ms 11372 KB Output is correct
13 Correct 304 ms 11276 KB Output is correct
14 Correct 971 ms 8856 KB Output is correct
15 Correct 1152 ms 8516 KB Output is correct
16 Correct 726 ms 7412 KB Output is correct
17 Correct 1058 ms 8660 KB Output is correct
18 Correct 888 ms 8212 KB Output is correct
19 Correct 1233 ms 15308 KB Output is correct
20 Correct 3455 ms 11816 KB Output is correct
21 Correct 516 ms 12972 KB Output is correct
22 Correct 3621 ms 13144 KB Output is correct
23 Correct 297 ms 12832 KB Output is correct
24 Correct 1527 ms 10164 KB Output is correct
25 Correct 2860 ms 14240 KB Output is correct
26 Correct 2286 ms 14660 KB Output is correct
27 Correct 2064 ms 13912 KB Output is correct
28 Correct 870 ms 36212 KB Output is correct
29 Correct 1823 ms 38920 KB Output is correct
30 Correct 4595 ms 30124 KB Output is correct
31 Correct 3923 ms 29620 KB Output is correct
32 Correct 753 ms 29348 KB Output is correct
33 Correct 1105 ms 29404 KB Output is correct
34 Correct 338 ms 32688 KB Output is correct
35 Correct 1765 ms 23920 KB Output is correct
36 Correct 3447 ms 36808 KB Output is correct
37 Correct 2739 ms 36972 KB Output is correct
38 Correct 2567 ms 36432 KB Output is correct
39 Correct 1214 ms 65684 KB Output is correct
40 Correct 2908 ms 67580 KB Output is correct
41 Correct 7060 ms 57056 KB Output is correct
42 Correct 6206 ms 55560 KB Output is correct
43 Correct 683 ms 62328 KB Output is correct
44 Correct 1241 ms 52960 KB Output is correct
45 Correct 2251 ms 30812 KB Output is correct
46 Correct 4438 ms 66304 KB Output is correct
47 Correct 4481 ms 66372 KB Output is correct
48 Correct 3979 ms 65880 KB Output is correct
49 Correct 1 ms 212 KB Output is correct