oj.uz

Submission #626132

# Submission time Handle Problem Language Result Execution time Memory
626132 2022-08-11T08:57:41 Z PoonYaPat Game (IOI13_game) C++14
37 / 100
 13000 ms 256000 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int r,c;
map<pii,ll> s;

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(ll x, ll y) {
    if (x==0) return y;
    if (y==0) return x;
    return gcd2(x,y);
}

void init(int R, int C) {
    r=R;
    c=C;
}

void update_y(int lx, int rx, int idx_x, int ly, int ry, int idx_y, int x, int y, ll val) {
    if (ly>y || ry<y) return;
    if (ly==ry) {
        if (lx==rx) {
            s[pii(idx_x,idx_y)]=val;
        } else {
            s[pii(idx_x,idx_y)]=gcd(s[pii(2*idx_x,idx_y)],s[pii(2*idx_x+1,idx_y)]);
        }
    } else {
        int mid=(ly+ry)/2;
        update_y(lx,rx,idx_x,ly,mid,2*idx_y,x,y,val);
        update_y(lx,rx,idx_x,mid+1,ry,2*idx_y+1,x,y,val);
        s[pii(idx_x,idx_y)]=gcd(s[pii(idx_x,2*idx_y)],s[pii(idx_x,2*idx_y+1)]);
    }
}

void update_x(int lx, int rx, int idx_x, int x, int y, ll val) {
    if (lx>x || rx<x) return;
    if (lx!=rx) {
        int mid=(lx+rx)/2;
        update_x(lx,mid,2*idx_x,x,y,val);
        update_x(mid+1,rx,2*idx_x+1,x,y,val);
    }
    update_y(lx,rx,idx_x,1,c,1,x,y,val);
}

void update(int P, int Q, long long K) {
    ++P; ++Q;
    update_x(1,r,1,P,Q,K);
}

ll query_y(int idx_x, int ly, int ry, int idx_y, int y1, int y2) {
    if (y1>ry || y2<ly) return 0;
    if (y1<=ly && ry<=y2) return s[pii(idx_x,idx_y)];
    int mid=(ly+ry)/2;
    return gcd(query_y(idx_x,ly,mid,2*idx_y,y1,y2),query_y(idx_x,mid+1,ry,2*idx_y+1,y1,y2));
}

ll query_x(int lx, int rx, int idx_x, int x1, int y1, int x2, int y2) {
    if (x1>rx || x2<lx) return 0;
    if (x1<=lx && rx<=x2) return query_y(idx_x,1,c,1,y1,y2);
    int mid=(lx+rx)/2;
    return gcd(query_x(lx,mid,2*idx_x,x1,y1,x2,y2),query_x(mid+1,rx,2*idx_x+1,x1,y1,x2,y2));
}

long long calculate(int P, int Q, int U, int V) {
    ++P; ++Q; ++U; ++V;
    if (P>U) swap(P,U);
    if (Q>V) swap(Q,V);
    return query_x(1,r,1,P,Q,U,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 684 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 4 ms 684 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 340 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 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5263 ms 44676 KB Output is correct
5 Correct 2892 ms 38508 KB Output is correct
6 Correct 4800 ms 102560 KB Output is correct
7 Correct 4828 ms 102360 KB Output is correct
8 Correct 3848 ms 97356 KB Output is correct
9 Correct 4838 ms 104496 KB Output is correct
10 Correct 4702 ms 102108 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 684 KB Output is correct
3 Correct 5 ms 688 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 6430 ms 48272 KB Output is correct
13 Correct 6432 ms 21532 KB Output is correct
14 Correct 3475 ms 7536 KB Output is correct
15 Correct 7609 ms 31360 KB Output is correct
16 Correct 985 ms 66352 KB Output is correct
17 Correct 10689 ms 252716 KB Output is correct
18 Runtime error 10886 ms 256000 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 700 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 4066 ms 44648 KB Output is correct
13 Correct 2454 ms 38540 KB Output is correct
14 Correct 4925 ms 102592 KB Output is correct
15 Correct 4431 ms 102360 KB Output is correct
16 Correct 3567 ms 97388 KB Output is correct
17 Correct 4306 ms 104524 KB Output is correct
18 Correct 4641 ms 102052 KB Output is correct
19 Correct 7004 ms 48272 KB Output is correct
20 Correct 6188 ms 21568 KB Output is correct
21 Correct 3894 ms 7420 KB Output is correct
22 Correct 8636 ms 31344 KB Output is correct
23 Correct 1024 ms 66312 KB Output is correct
24 Correct 12139 ms 252748 KB Output is correct
25 Execution timed out 13083 ms 256000 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 688 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 304 KB Output is correct
12 Correct 4626 ms 44736 KB Output is correct
13 Correct 2556 ms 38452 KB Output is correct
14 Correct 4540 ms 102508 KB Output is correct
15 Correct 4398 ms 102300 KB Output is correct
16 Correct 3599 ms 97388 KB Output is correct
17 Correct 4981 ms 104520 KB Output is correct
18 Correct 4796 ms 102036 KB Output is correct
19 Correct 6435 ms 48304 KB Output is correct
20 Correct 5774 ms 21596 KB Output is correct
21 Correct 3395 ms 7404 KB Output is correct
22 Correct 7834 ms 31404 KB Output is correct
23 Correct 965 ms 66308 KB Output is correct
24 Correct 10673 ms 252836 KB Output is correct
25 Runtime error 11169 ms 256000 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -