oj.uz

Submission #400302

# Submission time Handle Problem Language Result Execution time Memory
400302 2021-05-07T20:10:27 Z Antekb Game (IOI13_game) C++14
100 / 100
 9607 ms 28564 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=(1<<30), M=5e6, K=682005;

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;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int wsk1=1;
int l1[M], r1[M], Rank[M], Key[M];
ll val1[M], g[M];
/*struct node{
    node* l=nullptr, *r=nullptr;
    int Rank, Key;
    ll val, g;
    node(int _Key, ll _val): Key(_Key), val(_val), g(_val) {Rank=rng();}
    
};*/
void upd(int v){
    g[v]=val1[v];
    if(l1[v])g[v]=gcd2(g[l1[v]], g[v]);
    if(r1[v])g[v]=gcd2(g[r1[v]], g[v]);
}
int merge(int u, int v){
    if(!u)return v;
    if(!v)return u;
    assert(Key[u] < Key[v]);
    if(Rank[v]>Rank[u]){
        l1[v]=merge(u, l1[v]);
        upd(v);
        return v;
    }
    else{
        r1[u]=merge(r1[u], v);
        upd(u);
        return u;
    }
}
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
typedef pair<int, int> pnn;
pnn split(int v, int l){
    if(!v)return mp(0, 0);
    if(Key[v]<l){
        pnn a=split(r1[v], l);
        r1[v]=a.st;
        upd(v);
        a.st=v;
        return a;
    }
    else{
        pnn a=split(l1[v], l);
        l1[v]=a.nd;
        upd(v);
        a.nd=v;
        return a;
    }
}
void wyp(int v){
    if(!v) return;
    wyp(l1[v]);
    cout<<Rank[v]<<" "<<Key[v]<<" "<<val1[v]<<" "<<g[v]<<"\n";
    wyp(r1[v]);
}
/*int wsk1=1;
int l1[M], r1[M];
ll val1[M];

void upd(int v){
    if(!v)return;
    val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
    if(!v)return 0;
    //cout<<L<<" "<<R<<" "<<v->val<<"q\n";
    if(l==L && r==R){
        return val1[v];
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
    return ans;
}*/
ll quer1d(int v, int l, int r){
    //wyp(v);
    //cout<<l<<" "<<r<<"\n";

    pnn a=split(v, l);
    pnn b=split(a.nd, r+1);
    ll ans=0;
    if(b.st){
        ans=g[b.st];
        assert(Key[b.st] >=l && Key[b.st] <=r);
    }
    a.nd=merge(b.st, b.nd);
    assert(merge(a.st, a.nd)==v);
    //cout<<ans<<"\n";
    return ans;
}
/*int upd1d(int v, int L, int R, int i, ll val){
    if(!v)v=wsk1++;
    if(L==R){
        //cout<<v->val<<" "<<val<<" "<<i<<"u\n";
        val1[v]=val;
        return v;
    }
    //cout<<L<<" "<<R<<" "<<v->val<<"a\n";
    int M=(L+R)>>1;
    if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
    else r1[v]=upd1d(r1[v], M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"b\n";
    return v;
}*/
int upd1d(int v, int i, ll val){
    pnn a=split(v, i);
    pnn b=split(a.nd, i+1);
    if(b.st){
        assert(Key[b.st] == i);
        val1[b.st]=val;
    }
    else{
        b.st=wsk1;
        val1[wsk1]=val;
        g[wsk1]=val;
        Key[wsk1]=i;
        Rank[wsk1]=rng();
        wsk1++;
    }
    upd(b.st);
    a.nd=merge(b.st, b.nd);
    return merge(a.st, a.nd);
}

int wsk2=1;
int l2[K], r2[K];
int nodes[K];
ll quer2d(int v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(nodes[v], x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
    return ans;
}

int upd2d(int v, int L, int R, int i, int j, ll val){
    if(!v)v=wsk2++;
    if(L==R){
        //cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
        nodes[v]=upd1d(nodes[v], j, val);
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
    else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
    //cout<<L<<" "<<R<<" "<<i<<" "<<j<<"\n";
    nodes[v]=upd1d(nodes[v], j, gcd2(quer1d(nodes[l2[v]], j, j), quer1d(nodes[r2[v]], j, j)));
    return v;
}
int root=0;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    root=upd2d(root, 0, N-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return quer2d(root, 0, N-1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 7 ms 404 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2259 ms 13580 KB Output is correct
5 Correct 1447 ms 14240 KB Output is correct
6 Correct 3420 ms 10780 KB Output is correct
7 Correct 3861 ms 10364 KB Output is correct
8 Correct 2055 ms 6532 KB Output is correct
9 Correct 3699 ms 10576 KB Output is correct
10 Correct 3386 ms 10060 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 2450 ms 7432 KB Output is correct
13 Correct 4807 ms 3140 KB Output is correct
14 Correct 834 ms 904 KB Output is correct
15 Correct 5045 ms 3896 KB Output is correct
16 Correct 1891 ms 5352 KB Output is correct
17 Correct 2964 ms 4428 KB Output is correct
18 Correct 5343 ms 5652 KB Output is correct
19 Correct 4683 ms 5896 KB Output is correct
20 Correct 4152 ms 5124 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 2286 ms 13624 KB Output is correct
13 Correct 1441 ms 13892 KB Output is correct
14 Correct 3405 ms 10676 KB Output is correct
15 Correct 3858 ms 10736 KB Output is correct
16 Correct 2083 ms 6732 KB Output is correct
17 Correct 3739 ms 10692 KB Output is correct
18 Correct 3362 ms 10180 KB Output is correct
19 Correct 2475 ms 7504 KB Output is correct
20 Correct 4720 ms 3032 KB Output is correct
21 Correct 849 ms 1032 KB Output is correct
22 Correct 5061 ms 3860 KB Output is correct
23 Correct 1792 ms 5232 KB Output is correct
24 Correct 2958 ms 4312 KB Output is correct
25 Correct 5157 ms 5704 KB Output is correct
26 Correct 4599 ms 5840 KB Output is correct
27 Correct 4137 ms 5404 KB Output is correct
28 Correct 1324 ms 12688 KB Output is correct
29 Correct 3063 ms 15780 KB Output is correct
30 Correct 5338 ms 10732 KB Output is correct
31 Correct 4702 ms 8456 KB Output is correct
32 Correct 757 ms 944 KB Output is correct
33 Correct 1112 ms 1272 KB Output is correct
34 Correct 1825 ms 12980 KB Output is correct
35 Correct 2746 ms 7540 KB Output is correct
36 Correct 5983 ms 13204 KB Output is correct
37 Correct 4646 ms 13248 KB Output is correct
38 Correct 4654 ms 12740 KB Output is correct
39 Correct 3706 ms 10500 KB Output is correct
40 Correct 1 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 2288 ms 13676 KB Output is correct
13 Correct 1406 ms 14044 KB Output is correct
14 Correct 3360 ms 10712 KB Output is correct
15 Correct 3827 ms 10484 KB Output is correct
16 Correct 2015 ms 6732 KB Output is correct
17 Correct 3747 ms 10432 KB Output is correct
18 Correct 3345 ms 10184 KB Output is correct
19 Correct 2437 ms 7568 KB Output is correct
20 Correct 4765 ms 3012 KB Output is correct
21 Correct 830 ms 1120 KB Output is correct
22 Correct 5018 ms 4032 KB Output is correct
23 Correct 1782 ms 5264 KB Output is correct
24 Correct 2966 ms 4428 KB Output is correct
25 Correct 5167 ms 5520 KB Output is correct
26 Correct 4610 ms 5824 KB Output is correct
27 Correct 4085 ms 5268 KB Output is correct
28 Correct 1311 ms 12724 KB Output is correct
29 Correct 3055 ms 15916 KB Output is correct
30 Correct 5310 ms 10748 KB Output is correct
31 Correct 4666 ms 8388 KB Output is correct
32 Correct 731 ms 964 KB Output is correct
33 Correct 1093 ms 1144 KB Output is correct
34 Correct 1883 ms 12836 KB Output is correct
35 Correct 2778 ms 7496 KB Output is correct
36 Correct 5845 ms 13176 KB Output is correct
37 Correct 4391 ms 13336 KB Output is correct
38 Correct 4462 ms 12764 KB Output is correct
39 Correct 1931 ms 26440 KB Output is correct
40 Correct 6059 ms 28564 KB Output is correct
41 Correct 9607 ms 21932 KB Output is correct
42 Correct 8525 ms 16776 KB Output is correct
43 Correct 3238 ms 26672 KB Output is correct
44 Correct 1224 ms 1092 KB Output is correct
45 Correct 3690 ms 10600 KB Output is correct
46 Correct 8716 ms 27144 KB Output is correct
47 Correct 8646 ms 26920 KB Output is correct
48 Correct 8367 ms 26768 KB Output is correct
49 Correct 1 ms 332 KB Output is correct