oj.uz

Submission #427444

# Submission time Handle Problem Language Result Execution time Memory
427444 2021-06-14T15:21:22 Z arayi Game (IOI13_game) C++17
80 / 100
 7121 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
using namespace std;
 
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;
vector <int> l, r, e1;
vector <lli> e2;
vector <vector<int> > l1, r1;
vector <vector<lli> > t;
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]=l.size();
    else r[i-1]=l.size();
    l.ad(mod), r.ad(mod), l1.ad(e1), r1.ad(e1), t.ad(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 = ::l.size(), 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;
    e1.ad(mod), e2.ad(0);
    l.ad(mod), r.ad(mod);
    l1.ad(e1), r1.ad(e1), t.ad(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 1 ms 204 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 766 ms 13040 KB Output is correct
5 Correct 565 ms 13744 KB Output is correct
6 Correct 578 ms 9528 KB Output is correct
7 Correct 664 ms 9384 KB Output is correct
8 Correct 444 ms 8376 KB Output is correct
9 Correct 611 ms 9392 KB Output is correct
10 Correct 598 ms 8844 KB Output is correct
11 Correct 1 ms 292 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1322 ms 16504 KB Output is correct
13 Correct 1941 ms 8356 KB Output is correct
14 Correct 511 ms 3824 KB Output is correct
15 Correct 2347 ms 10000 KB Output is correct
16 Correct 383 ms 17272 KB Output is correct
17 Correct 1016 ms 11776 KB Output is correct
18 Correct 1909 ms 16988 KB Output is correct
19 Correct 1686 ms 17008 KB Output is correct
20 Correct 1595 ms 16372 KB Output is correct
21 Correct 1 ms 292 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 785 ms 12748 KB Output is correct
13 Correct 545 ms 13252 KB Output is correct
14 Correct 625 ms 9276 KB Output is correct
15 Correct 721 ms 8828 KB Output is correct
16 Correct 427 ms 7924 KB Output is correct
17 Correct 642 ms 8972 KB Output is correct
18 Correct 593 ms 8324 KB Output is correct
19 Correct 1456 ms 15640 KB Output is correct
20 Correct 2013 ms 7040 KB Output is correct
21 Correct 539 ms 3080 KB Output is correct
22 Correct 2450 ms 8732 KB Output is correct
23 Correct 399 ms 15812 KB Output is correct
24 Correct 1077 ms 10664 KB Output is correct
25 Correct 1991 ms 15636 KB Output is correct
26 Correct 1823 ms 15700 KB Output is correct
27 Correct 1776 ms 15148 KB Output is correct
28 Correct 1922 ms 167016 KB Output is correct
29 Correct 3404 ms 185964 KB Output is correct
30 Correct 7121 ms 132748 KB Output is correct
31 Correct 6766 ms 108116 KB Output is correct
32 Correct 1683 ms 10312 KB Output is correct
33 Correct 1818 ms 12824 KB Output is correct
34 Correct 1378 ms 180500 KB Output is correct
35 Correct 2320 ms 98208 KB Output is correct
36 Correct 4542 ms 184040 KB Output is correct
37 Correct 3678 ms 184180 KB Output is correct
38 Correct 3871 ms 183792 KB Output is correct
39 Correct 3152 ms 144796 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 725 ms 11360 KB Output is correct
13 Correct 546 ms 11712 KB Output is correct
14 Correct 677 ms 8020 KB Output is correct
15 Correct 663 ms 7808 KB Output is correct
16 Correct 425 ms 6692 KB Output is correct
17 Correct 633 ms 7828 KB Output is correct
18 Correct 595 ms 7212 KB Output is correct
19 Correct 1331 ms 14596 KB Output is correct
20 Correct 1949 ms 6300 KB Output is correct
21 Correct 471 ms 2284 KB Output is correct
22 Correct 2357 ms 8308 KB Output is correct
23 Correct 409 ms 15496 KB Output is correct
24 Correct 1022 ms 10488 KB Output is correct
25 Correct 2001 ms 15620 KB Output is correct
26 Correct 1653 ms 15688 KB Output is correct
27 Correct 1472 ms 15036 KB Output is correct
28 Correct 1715 ms 167576 KB Output is correct
29 Correct 3220 ms 186012 KB Output is correct
30 Correct 7044 ms 132684 KB Output is correct
31 Correct 6909 ms 108084 KB Output is correct
32 Correct 1679 ms 10400 KB Output is correct
33 Correct 1688 ms 12828 KB Output is correct
34 Correct 1328 ms 180280 KB Output is correct
35 Correct 2223 ms 98292 KB Output is correct
36 Correct 4614 ms 184060 KB Output is correct
37 Correct 3790 ms 184208 KB Output is correct
38 Correct 3886 ms 183656 KB Output is correct
39 Runtime error 2140 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -