oj.uz

Submission #766028

# Submission time Handle Problem Language Result Execution time Memory
766028 2023-06-25T09:09:49 Z fatemetmhr Game (IOI13_game) C++17
100 / 100
 5297 ms 128576 KB 
//  ~ Be Name Khoda ~  //
 
#include "game.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  2e7;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int tt = 0;
 
 
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;
}
 
namespace seg{
    int n, m, newnode = 2, innernode = 2, inner[maxnt];
    int chil[maxnt][2], innerchil[maxnt][2];
    ll g[maxnt];
    void innerupdbase(int l, int r, int id, ll val, int v){
        //cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
        if(r - l == 1){
            g[v] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!innerchil[v][0])
                innerchil[v][0] = innernode++;
            innerupdbase(l, mid, id, val, innerchil[v][0]);
        }
        else{
            if(!innerchil[v][1])
                innerchil[v][1] = innernode++;
            innerupdbase(mid, r, id, val, innerchil[v][1]);
        }
        g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
        //cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
    }
 
    void innerupdult(int l, int r, int id, int v1, int v2, int v3){
        g[v1] = gcd2(g[v2], g[v3]);
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!innerchil[v1][0])
                innerchil[v1][0] = innernode++;
            innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
        }
        else{
            if(!innerchil[v1][1])
                innerchil[v1][1] = innernode++;
            innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
        }
    }
 
 
    ll innerget(int l, int r, int lq, int rq, int v){
        if(v == 0 || rq <= l || r <= lq)
            return 0;
        if(lq <= l && r <= rq){
            //cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
            return g[v];
        }
        int mid = (l + r) >> 1;
        return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
    }
 
 
    void upd(int l, int r, int id, int id2, ll val, int v){
        if(!inner[v])
            inner[v] = innernode++;
        //cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
        if(r - l == 1){
            innerupdbase(0, m, id2, val, inner[v]);
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid){
            if(!chil[v][0])
                chil[v][0] = newnode++;
            upd(l, mid, id, id2, val, chil[v][0]);
        }
        else{
            if(!chil[v][1])
                chil[v][1] = newnode++;
            upd(mid, r, id, id2, val, chil[v][1]);
        }
        innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[chil[v][1]]);
    }
 
    ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
        if(v == 0 || rq <= l || r <= lq)
            return 0;
        if(lq <= l && r <= rq){
            if(!inner[v])
                return 0;
            ll ret = innerget(0, m, llq, rrq, inner[v]);
            //cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
            return ret;
        }
        int mid = (l + r) >> 1;
        return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
    }
 
    inline void clear(int nn, int mm){
        n = nn;
        m = mm;
        for(int i = 0; i < newnode; i++)
            inner[i] = chil[i][0] = chil[i][1] = 0;
        for(int i = 0; i < innernode; i++)
            innerchil[i][0] = innerchil[i][1] = g[i] = 0;
        newnode = innernode = 2;
    }
}
 
int szx, szy, n, m;
int newnode = 2, innernode = 2, inner[maxnt];
int chil[maxnt][2], innerchil[maxnt][2];
ll g[maxnt];
vector <int> avx, avy;
map <pair<int, int>, ll> av;
set <pair<int, int>> avseg;
 
void innerupdbase(int l, int r, int id, ll val, int v){
    //cout << "inner upd with " << l << ' ' << r << ' ' << id << ' ' << val << ' ' << v << endl;
    if(r - l == 1){
        g[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v][0])
            innerchil[v][0] = innernode++;
        innerupdbase(l, mid, id, val, innerchil[v][0]);
    }
    else{
        if(!innerchil[v][1])
            innerchil[v][1] = innernode++;
        innerupdbase(mid, r, id, val, innerchil[v][1]);
    }
    g[v] = gcd2(g[innerchil[v][0]], g[innerchil[v][1]]);
    //cout << "ok " << l << ' ' << r << ' ' << val << ' ' << v << ' ' << g[v] << ' ' << g[innerchil[v][1]] << ' ' << g[innerchil[v][0]] << endl;
}
 
void innerupdult(int l, int r, int id, int v1, int v2, int v3){
    g[v1] = gcd2(g[v2], g[v3]);
    if(r - l == 1)
        return;
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!innerchil[v1][0])
            innerchil[v1][0] = innernode++;
        innerupdult(l, mid, id, innerchil[v1][0], innerchil[v2][0], innerchil[v3][0]);
    }
    else{
        if(!innerchil[v1][1])
            innerchil[v1][1] = innernode++;
        innerupdult(mid, r, id, innerchil[v1][1], innerchil[v2][1], innerchil[v3][1]);
    }
}
 
 
ll innerget(int l, int r, int lq, int rq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        //cout << "inner getting " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << g[v] << endl;
        return g[v];
    }
    int mid = (l + r) >> 1;
    return gcd2(innerget(l, mid, lq, rq, innerchil[v][0]), innerget(mid, r, lq, rq, innerchil[v][1]));
}
 
 
void upd(int l, int r, int id, int id2, ll val, int v){
    if(!inner[v])
        inner[v] = innernode++;
    //cout << "entering iiner update " << l << ' ' << r << ' ' << v << ' ' << inner[v] << ' ' << val << endl;
    if(r - l == 1){
        innerupdbase(0, m, id2, val, inner[v]);
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid){
        if(!chil[v][0])
            chil[v][0] = newnode++;
        upd(l, mid, id, id2, val, chil[v][0]);
    }
    else{
        if(!chil[v][1])
            chil[v][1] = newnode++;
        upd(mid, r, id, id2, val, chil[v][1]);
    }
    innerupdult(0, m, id2, inner[v], inner[chil[v][0]], inner[chil[v][1]]);
}
 
ll get(int l, int r, int lq, int rq, int llq, int rrq, int v){
    if(v == 0 || rq <= l || r <= lq)
        return 0;
    if(lq <= l && r <= rq){
        if(!inner[v])
            return 0;
        ll ret = innerget(0, m, llq, rrq, inner[v]);
        //cout << "here " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << ret << endl;
        return ret;
    }
    int mid = (l + r) >> 1;
    return gcd2(get(l, mid, lq, rq, llq, rrq, chil[v][0]), get(mid, r, lq, rq, llq, rrq, chil[v][1]));
}
 
void init(int R, int C) {
    n = R;
    m = C;
    /* ... */
}
 
 
inline void rebuild(){
    sort(all(avx));
    sort(all(avy));
    avx.resize(unique(all(avx)) - avx.begin());
    avy.resize(unique(all(avy)) - avy.begin());
    szx = avx.size();
    szy = avy.size();
 
    for(int i = 0; i < newnode; i++)
        inner[i] = chil[i][0] = chil[i][1] = 0;
    for(int i = 0; i < innernode; i++)
        innerchil[i][0] = innerchil[i][1] = g[i] = 0;
    newnode = innernode = 2;
    seg::clear(szx, szy);
    for(auto it = av.begin(); it != av.end(); it++){
        avseg.insert(it->fi);
        int ptx = lower_bound(avx.begin(), avx.begin() + szx, (it->fi).fi) - avx.begin();
        int pty = lower_bound(avy.begin(), avy.begin() + szy, (it->fi).se) - avy.begin();
        seg::upd(0, szx, ptx, pty, it->se, 1);
    }
}

int opt = 0;

void update(int x, int y, long long k) {
    opt++;
    if(newnode > 5e6 || innernode > 5e6)
        rebuild();
    if(avseg.find(mp(x, y)) != avseg.end()){
        av[{x, y}] = k;
        x = lower_bound(avx.begin(), avx.begin() + szx, x) - avx.begin();
        y = lower_bound(avy.begin(), avy.begin() + szy, y) - avy.begin();
        seg::upd(0, szx, x, y, k, 1);
        return;
    }
    upd(0, n, x, y, k, 1);
    av[{x, y}] = k;
    avx.pb(x);
    avy.pb(y);
}
 
long long calculate(int l, int d, int r, int u) {

    tt++;
 
    ll ans = get(0, n, l, r + 1, d, u + 1, 1);
    //if(tt == 129048)
    //    cerr << l << ' ' << r << ' ' << d << ' ' << u << endl;
    l = lower_bound(avx.begin(), avx.begin() + szx, l) - avx.begin();
    r = upper_bound(avx.begin(), avx.begin() + szx, r) - avx.begin();
    d = lower_bound(avy.begin(), avy.begin() + szy, d) - avy.begin();
    u = upper_bound(avy.begin(), avy.begin() + szy, u) - avy.begin();
    ans = gcd2(ans, seg::get(0, szx, l, r, d, u, 1));
    //if(tt == 129048)
    //    cerr << newnode << ' ' << innernode << ' ' << ans << ' ' << opt << ' ' << l << ' ' << r << ' ' << d << ' ' << u << endl;
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 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 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 395 ms 11344 KB Output is correct
5 Correct 292 ms 12096 KB Output is correct
6 Correct 329 ms 8680 KB Output is correct
7 Correct 373 ms 8504 KB Output is correct
8 Correct 254 ms 7028 KB Output is correct
9 Correct 353 ms 8660 KB Output is correct
10 Correct 308 ms 8192 KB Output is correct
11 Correct 1 ms 340 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 340 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 628 ms 13252 KB Output is correct
13 Correct 1073 ms 6572 KB Output is correct
14 Correct 220 ms 3512 KB Output is correct
15 Correct 1283 ms 7832 KB Output is correct
16 Correct 136 ms 12708 KB Output is correct
17 Correct 549 ms 9236 KB Output is correct
18 Correct 802 ms 13040 KB Output is correct
19 Correct 751 ms 13308 KB Output is correct
20 Correct 718 ms 12596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 397 ms 11648 KB Output is correct
13 Correct 297 ms 11916 KB Output is correct
14 Correct 351 ms 8752 KB Output is correct
15 Correct 377 ms 8440 KB Output is correct
16 Correct 265 ms 7100 KB Output is correct
17 Correct 358 ms 8548 KB Output is correct
18 Correct 309 ms 8124 KB Output is correct
19 Correct 637 ms 13216 KB Output is correct
20 Correct 1072 ms 6540 KB Output is correct
21 Correct 226 ms 3512 KB Output is correct
22 Correct 1292 ms 8040 KB Output is correct
23 Correct 136 ms 12788 KB Output is correct
24 Correct 561 ms 9340 KB Output is correct
25 Correct 802 ms 13012 KB Output is correct
26 Correct 713 ms 13288 KB Output is correct
27 Correct 669 ms 12644 KB Output is correct
28 Correct 434 ms 89036 KB Output is correct
29 Correct 1398 ms 96448 KB Output is correct
30 Correct 4038 ms 89692 KB Output is correct
31 Correct 3149 ms 80952 KB Output is correct
32 Correct 379 ms 3628 KB Output is correct
33 Correct 500 ms 4960 KB Output is correct
34 Correct 280 ms 93600 KB Output is correct
35 Correct 853 ms 72996 KB Output is correct
36 Correct 2041 ms 93772 KB Output is correct
37 Correct 1454 ms 93892 KB Output is correct
38 Correct 1440 ms 93288 KB Output is correct
39 Correct 1118 ms 93752 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.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 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 398 ms 11732 KB Output is correct
13 Correct 278 ms 11920 KB Output is correct
14 Correct 319 ms 8708 KB Output is correct
15 Correct 348 ms 8468 KB Output is correct
16 Correct 253 ms 7104 KB Output is correct
17 Correct 370 ms 8612 KB Output is correct
18 Correct 312 ms 8180 KB Output is correct
19 Correct 632 ms 13224 KB Output is correct
20 Correct 1074 ms 6584 KB Output is correct
21 Correct 219 ms 3564 KB Output is correct
22 Correct 1298 ms 8084 KB Output is correct
23 Correct 138 ms 12748 KB Output is correct
24 Correct 542 ms 9248 KB Output is correct
25 Correct 773 ms 13140 KB Output is correct
26 Correct 701 ms 13252 KB Output is correct
27 Correct 663 ms 12588 KB Output is correct
28 Correct 431 ms 89016 KB Output is correct
29 Correct 1348 ms 96332 KB Output is correct
30 Correct 3978 ms 89616 KB Output is correct
31 Correct 3206 ms 80944 KB Output is correct
32 Correct 375 ms 3768 KB Output is correct
33 Correct 491 ms 5064 KB Output is correct
34 Correct 267 ms 93388 KB Output is correct
35 Correct 809 ms 73052 KB Output is correct
36 Correct 1939 ms 93696 KB Output is correct
37 Correct 1433 ms 93952 KB Output is correct
38 Correct 1400 ms 93384 KB Output is correct
39 Correct 628 ms 103200 KB Output is correct
40 Correct 2116 ms 121608 KB Output is correct
41 Correct 5297 ms 102840 KB Output is correct
42 Correct 4543 ms 102160 KB Output is correct
43 Correct 544 ms 124476 KB Output is correct
44 Correct 461 ms 10952 KB Output is correct
45 Correct 1278 ms 101576 KB Output is correct
46 Correct 2969 ms 128576 KB Output is correct
47 Correct 2810 ms 128524 KB Output is correct
48 Correct 2704 ms 128168 KB Output is correct
49 Correct 1 ms 340 KB Output is correct