oj.uz

Submission #427434

# Submission time Handle Problem Language Result Execution time Memory
427434 2021-06-14T15:12:28 Z arayi Game (IOI13_game) C++17
63 / 100
 2669 ms 189796 KB 
#include "game.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
using namespace std;
const int N = 1e5 + 30;
const int mod = 1e9;
long long gcd2(long long X, long long Y) {
    while (X != Y && Y != 0) {
        X %= Y; swap(X, Y);
    }
    return X;
}
int n, m, ii;
int l[N], r[N];
vector <int> e1;
vector <lli> e2;
vector<int> l1[N], r1[N];
vector<lli> t[N];
map <pair<int, int>, lli> mp;
lli qry1(int l, int r, int nd, int nl = 0, int nr = m - 1, int i1 = 0)
{
    if(l > nr || r < nl || i1 == mod) return 0;
    if(l == nl && r == nr) return t[nd][i1];
    int mid = (nl + nr) / 2;
    return gcd2(qry1(l, min(mid, r), nd, nl, mid, l1[nd][i1]), 
        qry1(max(mid + 1, l), r, nd, mid + 1, nr, r1[nd][i1]));
}
lli qry(int l, int r, int l1, int r1, int nl = 0, int nr = n - 1, int nd = 0)
{
    if(l > nr || r < nl || nd == mod) return 0;
    if(l == nl && r == nr) return qry1(l1, r1, nd);
    int mid = (nl + nr) / 2;
    return gcd2(qry(l, min(mid, r), l1, r1, nl, mid, ::l[nd]),
        qry(max(mid + 1, l), r, l1, r1, mid + 1, nr, ::r[nd]));
}
void push1(int nd, int i)
{
    if(i < 0) l1[nd][-i-1]=l1[nd].size();
    else r1[nd][i-1]=l1[nd].size();
    l1[nd].ad(mod);
    r1[nd].ad(mod);
    t[nd].ad(0);
}
void upd1(int l1, int r1, int R, int c, lli v, int nd, int l = 0, int r = m - 1, int i1 = 0, int par = 0)
{
    if(l > c || r < c) return;
    if(i1 == mod) i1 = ::l1[nd].size(), push1(nd, par);
    if(l == r) 
    {
        if(mp[make_pair(R, c)] == 0) 
        {
            t[nd][i1] = gcd2(t[nd][i1], v);
            return;
        }
        t[nd][i1] = v;
        if(l1 < R) t[nd][i1] = gcd2(t[nd][i1], qry(l1, R - 1, l, l));
        if(r1 > R) t[nd][i1] = gcd2(t[nd][i1], qry(R + 1, r1, l, l));
        return;
    }
    int mid = (l + r) / 2;
    upd1(l1, r1, R, c, v, nd, l, mid, ::l1[nd][i1], -i1-1);
    upd1(l1, r1, R, c, v, nd, mid + 1, r, ::r1[nd][i1], i1+1);
    t[nd][i1] = 0;
    if(::l1[nd][i1]!= mod) t[nd][i1] = t[nd][::l1[nd][i1]];
    if(::r1[nd][i1]!= mod) t[nd][i1] = gcd2(t[nd][i1], t[nd][::r1[nd][i1]]);
}
void push(int i)
{
    if(i < 0) l[-i-1]=ii;
    else r[i-1]=ii;
    l[ii]=r[ii]=mod;
    l1[ii]=r1[ii]=e1;
    t[ii++]=e2;
}
void upd(int r1, int c, lli v, int l = 0, int r = n - 1, int nd = 0, int par = 0)
{
    if(l > r1 || r < r1) return;
    if(nd == mod) nd = ii, push(par);
    upd1(l, r, r1, c, v, nd);
    if(l==r) return;
    int mid = (l + r) / 2;
    upd(r1, c, v, l, mid, ::l[nd], -nd-1);
    upd(r1, c, v, mid + 1, r, ::r[nd], nd+1);
}
void init(int R, int C) 
{
    n = R, m = C;
    ii++;
    e1.ad(mod), e2.ad(0);
    l[0] = r[0] = mod;
    l1[0] = r1[0] = e1;
    t[0] = e2;
}

void update(int P, int Q, long long K) 
{
    upd(P, Q, K);
    mp[make_pair(P, Q)]=K;
}

long long calculate(int P, int Q, int U, int V) {
    return qry(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7340 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 7 ms 7336 KB Output is correct
4 Correct 7 ms 7244 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 8 ms 7440 KB Output is correct
7 Correct 6 ms 7340 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 7 ms 7344 KB Output is correct
10 Correct 6 ms 7344 KB Output is correct
11 Correct 7 ms 7356 KB Output is correct
12 Correct 6 ms 7348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 5 ms 7256 KB Output is correct
3 Correct 6 ms 7244 KB Output is correct
4 Correct 962 ms 20456 KB Output is correct
5 Correct 663 ms 20372 KB Output is correct
6 Correct 737 ms 16920 KB Output is correct
7 Correct 913 ms 16972 KB Output is correct
8 Correct 506 ms 15404 KB Output is correct
9 Correct 734 ms 16908 KB Output is correct
10 Correct 794 ms 16148 KB Output is correct
11 Correct 6 ms 7344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 9 ms 7436 KB Output is correct
3 Correct 8 ms 7372 KB Output is correct
4 Correct 6 ms 7344 KB Output is correct
5 Correct 8 ms 7348 KB Output is correct
6 Correct 8 ms 7344 KB Output is correct
7 Correct 5 ms 7344 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 6 ms 7344 KB Output is correct
10 Correct 7 ms 7300 KB Output is correct
11 Correct 7 ms 7320 KB Output is correct
12 Correct 1410 ms 23196 KB Output is correct
13 Correct 2008 ms 14704 KB Output is correct
14 Correct 522 ms 10860 KB Output is correct
15 Correct 2513 ms 16896 KB Output is correct
16 Correct 315 ms 24060 KB Output is correct
17 Correct 1161 ms 19004 KB Output is correct
18 Correct 2410 ms 24480 KB Output is correct
19 Correct 1971 ms 24488 KB Output is correct
20 Correct 1766 ms 23924 KB Output is correct
21 Correct 5 ms 7264 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7264 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7244 KB Output is correct
5 Correct 5 ms 7340 KB Output is correct
6 Correct 6 ms 7460 KB Output is correct
7 Correct 6 ms 7348 KB Output is correct
8 Correct 5 ms 7296 KB Output is correct
9 Correct 11 ms 7324 KB Output is correct
10 Correct 7 ms 7372 KB Output is correct
11 Correct 5 ms 7344 KB Output is correct
12 Correct 837 ms 20908 KB Output is correct
13 Correct 585 ms 20604 KB Output is correct
14 Correct 580 ms 17540 KB Output is correct
15 Correct 745 ms 17532 KB Output is correct
16 Correct 452 ms 15728 KB Output is correct
17 Correct 628 ms 17848 KB Output is correct
18 Correct 650 ms 16912 KB Output is correct
19 Correct 1402 ms 23660 KB Output is correct
20 Correct 1970 ms 15204 KB Output is correct
21 Correct 467 ms 11972 KB Output is correct
22 Correct 2669 ms 17844 KB Output is correct
23 Correct 324 ms 25116 KB Output is correct
24 Correct 1194 ms 20684 KB Output is correct
25 Correct 2245 ms 26476 KB Output is correct
26 Correct 1728 ms 26692 KB Output is correct
27 Correct 1584 ms 26180 KB Output is correct
28 Runtime error 1269 ms 189796 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7244 KB Output is correct
2 Correct 7 ms 7336 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7344 KB Output is correct
5 Correct 6 ms 7344 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 8 ms 7340 KB Output is correct
9 Correct 7 ms 7344 KB Output is correct
10 Correct 6 ms 7372 KB Output is correct
11 Correct 6 ms 7348 KB Output is correct
12 Correct 751 ms 20768 KB Output is correct
13 Correct 635 ms 20756 KB Output is correct
14 Correct 719 ms 17568 KB Output is correct
15 Correct 682 ms 17496 KB Output is correct
16 Correct 461 ms 15668 KB Output is correct
17 Correct 701 ms 17556 KB Output is correct
18 Correct 685 ms 16796 KB Output is correct
19 Correct 1291 ms 23376 KB Output is correct
20 Correct 1939 ms 14644 KB Output is correct
21 Correct 565 ms 10824 KB Output is correct
22 Correct 2531 ms 16512 KB Output is correct
23 Correct 273 ms 23496 KB Output is correct
24 Correct 1196 ms 18556 KB Output is correct
25 Correct 2102 ms 24236 KB Output is correct
26 Correct 1566 ms 24896 KB Output is correct
27 Correct 1773 ms 23836 KB Output is correct
28 Runtime error 1254 ms 187280 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -