oj.uz

Submission #599969

# Submission time Handle Problem Language Result Execution time Memory
599969 2022-07-20T10:55:42 Z AmirElarbi Game (IOI13_game) C++14
37 / 100
 1254 ms 256000 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
const int MOD = 1e9;
const int nax = 2e3+5;
#include "game.h"
ll n,m;
ve<ve<ll>> t;
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;
}

ll gcd_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) 
        return 0ll;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return gcd2( gcd_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         , gcd_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}

ll gcd_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return gcd_y(vx, 1, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    return gcd2(gcd_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         , gcd_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, ll new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = gcd2(t[vx*2][vy] , t[vx*2+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = gcd2(t[vx][vy*2] , t[vx][vy*2+1]);
    }
}

void update_x(int vx, int lx, int rx, int x, int y, ll new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
}

void init(int R, int C) {
    ve<ll> tm(C*4,0);
    for (int i = 0; i < R*4; ++i)
    {
        t.pb(tm);
    }
    n = R, m = C;
}

void update(int P, int Q, long long K) {
    update_x(1,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return gcd_x(1,0,n-1,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 590 ms 129680 KB Output is correct
5 Correct 452 ms 131068 KB Output is correct
6 Correct 575 ms 128844 KB Output is correct
7 Correct 551 ms 131092 KB Output is correct
8 Correct 460 ms 131472 KB Output is correct
9 Correct 573 ms 131108 KB Output is correct
10 Correct 515 ms 130944 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 812 ms 129764 KB Output is correct
13 Correct 1186 ms 126588 KB Output is correct
14 Runtime error 98 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 575 ms 129704 KB Output is correct
13 Correct 467 ms 133828 KB Output is correct
14 Correct 528 ms 131488 KB Output is correct
15 Correct 565 ms 131084 KB Output is correct
16 Correct 489 ms 131512 KB Output is correct
17 Correct 570 ms 131240 KB Output is correct
18 Correct 534 ms 130724 KB Output is correct
19 Correct 800 ms 133916 KB Output is correct
20 Correct 1218 ms 130392 KB Output is correct
21 Runtime error 100 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1536 KB Output is correct
12 Correct 578 ms 129708 KB Output is correct
13 Correct 448 ms 133860 KB Output is correct
14 Correct 544 ms 131308 KB Output is correct
15 Correct 556 ms 131084 KB Output is correct
16 Correct 465 ms 131400 KB Output is correct
17 Correct 553 ms 131156 KB Output is correct
18 Correct 522 ms 130832 KB Output is correct
19 Correct 842 ms 134064 KB Output is correct
20 Correct 1254 ms 130556 KB Output is correct
21 Runtime error 101 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -