oj.uz

Submission #427439

# Submission time Handle Problem Language Result Execution time Memory
427439 2021-06-14T15:15:47 Z arayi Game (IOI13_game) C++17
63 / 100
 2455 ms 190600 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 5 ms 7244 KB Output is correct
2 Correct 6 ms 7344 KB Output is correct
3 Correct 6 ms 7340 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 7 ms 7264 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 6 ms 7240 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 6 ms 7348 KB Output is correct
10 Correct 7 ms 7296 KB Output is correct
11 Correct 6 ms 7372 KB Output is correct
12 Correct 7 ms 7244 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7236 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 7340 KB Output is correct
4 Correct 785 ms 21876 KB Output is correct
5 Correct 626 ms 21568 KB Output is correct
6 Correct 627 ms 18596 KB Output is correct
7 Correct 657 ms 18544 KB Output is correct
8 Correct 432 ms 16640 KB Output is correct
9 Correct 664 ms 18748 KB Output is correct
10 Correct 611 ms 17804 KB Output is correct
11 Correct 6 ms 7264 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7264 KB Output is correct
2 Correct 8 ms 7368 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7268 KB Output is correct
5 Correct 6 ms 7320 KB Output is correct
6 Correct 6 ms 7344 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 6 ms 7356 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 6 ms 7388 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 1253 ms 24408 KB Output is correct
13 Correct 2007 ms 15976 KB Output is correct
14 Correct 489 ms 12680 KB Output is correct
15 Correct 2367 ms 18368 KB Output is correct
16 Correct 269 ms 25396 KB Output is correct
17 Correct 1074 ms 20892 KB Output is correct
18 Correct 1776 ms 26756 KB Output is correct
19 Correct 1434 ms 26848 KB Output is correct
20 Correct 1532 ms 26188 KB Output is correct
21 Correct 7 ms 7244 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 6 ms 7340 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 6 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 6 ms 7372 KB Output is correct
7 Correct 8 ms 7344 KB Output is correct
8 Correct 5 ms 7232 KB Output is correct
9 Correct 7 ms 7500 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 8 ms 7340 KB Output is correct
12 Correct 743 ms 21928 KB Output is correct
13 Correct 575 ms 21632 KB Output is correct
14 Correct 665 ms 18700 KB Output is correct
15 Correct 622 ms 18528 KB Output is correct
16 Correct 446 ms 16680 KB Output is correct
17 Correct 663 ms 18696 KB Output is correct
18 Correct 571 ms 17888 KB Output is correct
19 Correct 1239 ms 24368 KB Output is correct
20 Correct 1875 ms 15900 KB Output is correct
21 Correct 559 ms 12668 KB Output is correct
22 Correct 2455 ms 18600 KB Output is correct
23 Correct 304 ms 25316 KB Output is correct
24 Correct 1004 ms 20796 KB Output is correct
25 Correct 1827 ms 26656 KB Output is correct
26 Correct 1600 ms 26780 KB Output is correct
27 Correct 1350 ms 26180 KB Output is correct
28 Runtime error 926 ms 190104 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 5 ms 7244 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 7 ms 7372 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 8 ms 7376 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 7 ms 7244 KB Output is correct
9 Correct 6 ms 7340 KB Output is correct
10 Correct 6 ms 7348 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 726 ms 21900 KB Output is correct
13 Correct 582 ms 21672 KB Output is correct
14 Correct 543 ms 18616 KB Output is correct
15 Correct 604 ms 18592 KB Output is correct
16 Correct 440 ms 16792 KB Output is correct
17 Correct 612 ms 18592 KB Output is correct
18 Correct 546 ms 17796 KB Output is correct
19 Correct 1210 ms 24380 KB Output is correct
20 Correct 1927 ms 15876 KB Output is correct
21 Correct 495 ms 12672 KB Output is correct
22 Correct 2217 ms 18408 KB Output is correct
23 Correct 277 ms 25280 KB Output is correct
24 Correct 912 ms 20824 KB Output is correct
25 Correct 1759 ms 26748 KB Output is correct
26 Correct 1465 ms 26788 KB Output is correct
27 Correct 1441 ms 26196 KB Output is correct
28 Runtime error 745 ms 190600 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -