oj.uz

Submission #98837

# Submission time Handle Problem Language Result Execution time Memory
98837 2019-02-26T11:49:08 Z Alexa2001 Game (IOI13_game) C++17
36 / 100
 4913 ms 96444 KB 
#include "game.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

typedef long long ll;
const int Nmax = 2005;

int N, M, Nr100, Nr10, Y1, Y2;
ll ans, a[Nmax + 200][Nmax + 200];


ll gcd2(ll X, ll Y)
{
    if(!Y) return X;
    ll rest = X % Y;
    while(rest)
        X = Y, Y = rest, rest = X % Y;
    return Y;
}


class SegTree
{
    ll a[Nmax<<2];
public:
    void update(int node, int st, int dr, int pos, ll val)
    {
        if(st == dr)
        {
            a[node] = val;
            return;
        }
        if(pos <= mid) update(left_son, st, mid, pos, val);
            else update(right_son, mid+1, dr, pos, val);
        a[node] = gcd2(a[left_son], a[right_son]);
    }

    void query(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R)
        {
            ans = gcd2(a[node], ans);
            return;
        }
        if(L <= mid) query(left_son, st, mid, L, R);
        if(mid < R) query(right_son, mid+1, dr, L, R);
    }
} aint[2 * Nmax];




void init(int R, int C)
{
    if(!(R <= 2000 && C <= 2000)) exit(0);
    N = R; M = C;

    Nr100 = (R-1) / 100 + 1;
    Nr10 = (R-1) / 10 + 1;
}

int up(int x, int y) /// primul multiplu de y care e >= x
{
    return (x + y - 1) / y;
}
int down(int x, int y)
{
    if(x + 1 - y < 0) return -1;
    return (x - y + 1) / y;
}

void update(int x, int y, ll K)
{
    a[x][y] = K;

    int i, id;
    ll val;

    id = x / 100; val = 0;
    for(i = id*100; i < id*100 + 100; ++i) val = gcd2(a[i][y], val);
    aint[id].update(1, 0, M-1, y, val);

    id = x / 10; val = 0;
    for(i = id*10; i < id*10 + 10; ++i) val = gcd2(a[i][y], val);
    aint[id + Nr100].update(1, 0, M-1, y, val);

    aint[x + Nr100 + Nr10].update(1, 0, M-1, y, K);
}

void query1(int l, int r)
{
    if(l > r) return;
    int i;
    for(i=l; i<=r; ++i)
        aint[Nr100 + Nr10 + i].query(1, 0, M-1, Y1, Y2);
}

void query10(int l, int r)
{
    if(l > r) return;
    int i, L = up(l, 10), R = down(r, 10);

    if(L > R)
    {
        query1(l, r);
        return;
    }

    for(i=L; i<=R; ++i)
        aint[i + Nr100].query(1, 0, M-1, Y1, Y2);

    query1(l, L * 10 - 1);
    query1(R * 10 + 10, r);
}

void query100(int l, int r)
{
    if(l > r) return;
    int i, L = up(l, 100), R = down(r, 100);

    if(L > R)
    {
        query10(l, r);
        return;
    }

    for(i=L; i<=R; ++i)
        aint[i].query(1, 0, M-1, Y1, Y2);

    query10(l, L * 100 - 1);
    query10(R * 100 + 100, r);
}

ll calculate(int P, int Q, int U, int V)
{
    int X1, X2;
    X1 = min(P, U);
    X2 = max(P, U);
    Y1 = min(Q, V);
    Y2 = max(Q, V);

    ans = 0;
    query100(X1, X2);
    return ans;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 0 ms 640 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2515 ms 39536 KB Output is correct
13 Correct 2746 ms 31096 KB Output is correct
14 Correct 1644 ms 6996 KB Output is correct
15 Correct 3949 ms 56424 KB Output is correct
16 Correct 464 ms 94664 KB Output is correct
17 Correct 3871 ms 73640 KB Output is correct
18 Correct 4695 ms 96444 KB Output is correct
19 Correct 4158 ms 96308 KB Output is correct
20 Correct 4913 ms 95460 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 4 ms 668 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -