oj.uz

Submission #40664

# Submission time Handle Problem Language Result Execution time Memory
40664 2018-02-06T16:21:39 Z top34051 Game (IOI13_game) C++14
10 / 100
 13000 ms 24224 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e7 + 5;
int R, C, sz = 1;
int rec[maxn][3];
ll seg[maxn];

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

class segtree {
public:
    int get(int pos, int dir) {
        if(!rec[pos][dir]) rec[pos][dir] = ++sz;
        return rec[pos][dir];
    }
    void row_update(int pos, int l, int r, int x, int y, ll val) {
//        printf("row_update [%d, %d] : (%d, %d) val = %lld\n",l,r,x,y,val);
        if(l>r || r<x || x<l) return ;
        col_update(get(pos,2), 1, C, y, val);
        if(l==r) return ;
        int mid = (l+r)/2;
        row_update(get(pos,0), l, mid, x, y, val);
        row_update(get(pos,1), mid+1, r, x, y, val);
    }
    void col_update(int pos, int l, int r, int x, ll val) {
//        printf("------- col_update [%d, %d] : (%d) val = %lld\n",l,r,x,val);
        if(l>r || r<x || x<l) return ;
        if(l==r) {
            seg[pos] = val;
//            printf("------- seg[%d, %d] = %lld\n",l,r,seg[pos]);
            return ;
        }
        int mid = (l+r)/2;
        col_update(get(pos,0), l, mid, x, val);
        col_update(get(pos,1), mid+1, r, x, val);
        seg[pos] = gcd2(seg[get(pos,0)], seg[get(pos,1)]);
//        printf("------- seg[%d, %d] = %lld (%lld and %lld)\n",l,r,seg[pos],seg[get(pos,0)],seg[get(pos,1)]);
    }
    ll row_query(int pos, int l, int r, int r1, int r2, int c1, int c2) {
        if(l>r || r<r1 || r2<l) return 0LL;
        if(r1<=l && r<=r2) return col_query(get(pos,2), 1, C, c1, c2);
        int mid = (l+r)/2;
        return gcd2(row_query(get(pos,0), l, mid, r1, r2, c1, c2), row_query(get(pos,1), mid+1, r, r1, r2, c1, c2));
    }
    ll col_query(int pos, int l, int r, int x, int y) {
        if(l>r || r<x || y<l) return 0LL;
        if(x<=l && r<=y) return seg[pos];
        int mid = (l+r)/2;
        return gcd2(col_query(get(pos,0), l, mid, x, y), col_query(get(pos,1), mid+1, r, x, y));
    }
    void update(int x, int y, ll val) {
        row_update(1, 1, R, x, y, val);
    }
    ll query(int r1, int r2, int c1, int c2) {
//        printf("QUERY (%d, %d) (%d, %d)\n",r1,r2,c1,c2);
//        return row_query(1, 1, R, r1, r2, c1, c2);
        int x,y;
        ll ans = 0;
        for(x=r1;x<=r2;x++) {
            for(y=c1;y<=c2;y++) {
                ans = gcd2(ans, row_query(1,1,R,x,x,y,y));
            }
        }
        return ans;
    }
};

segtree tree;

void init(int N, int M) {
    R = N; C = M;
}

void update(int P, int Q, ll K) {
    tree.update(P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return tree.query(P+1, U+1, Q+1, V+1);
}

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 2 ms 252 KB Output is correct
2 Correct 14 ms 736 KB Output is correct
3 Correct 23 ms 936 KB Output is correct
4 Correct 2 ms 936 KB Output is correct
5 Correct 20 ms 936 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 936 KB Output is correct
8 Correct 4 ms 936 KB Output is correct
9 Correct 3 ms 936 KB Output is correct
10 Correct 13 ms 940 KB Output is correct
11 Correct 27 ms 940 KB Output is correct
12 Correct 2 ms 940 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 940 KB Output is correct
2 Correct 1 ms 940 KB Output is correct
3 Correct 2 ms 940 KB Output is correct
4 Execution timed out 13011 ms 24072 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 24072 KB Output is correct
2 Correct 12 ms 24072 KB Output is correct
3 Correct 12 ms 24072 KB Output is correct
4 Correct 1 ms 24072 KB Output is correct
5 Correct 12 ms 24072 KB Output is correct
6 Correct 2 ms 24072 KB Output is correct
7 Correct 2 ms 24072 KB Output is correct
8 Correct 3 ms 24072 KB Output is correct
9 Correct 3 ms 24072 KB Output is correct
10 Correct 9 ms 24072 KB Output is correct
11 Correct 27 ms 24072 KB Output is correct
12 Execution timed out 13013 ms 24224 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 24224 KB Output is correct
2 Correct 13 ms 24224 KB Output is correct
3 Correct 21 ms 24224 KB Output is correct
4 Correct 1 ms 24224 KB Output is correct
5 Correct 16 ms 24224 KB Output is correct
6 Correct 2 ms 24224 KB Output is correct
7 Correct 2 ms 24224 KB Output is correct
8 Correct 5 ms 24224 KB Output is correct
9 Correct 3 ms 24224 KB Output is correct
10 Correct 9 ms 24224 KB Output is correct
11 Correct 27 ms 24224 KB Output is correct
12 Execution timed out 13057 ms 24224 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 24224 KB Output is correct
2 Correct 18 ms 24224 KB Output is correct
3 Correct 13 ms 24224 KB Output is correct
4 Correct 1 ms 24224 KB Output is correct
5 Correct 17 ms 24224 KB Output is correct
6 Correct 2 ms 24224 KB Output is correct
7 Correct 2 ms 24224 KB Output is correct
8 Correct 5 ms 24224 KB Output is correct
9 Correct 3 ms 24224 KB Output is correct
10 Correct 9 ms 24224 KB Output is correct
11 Correct 37 ms 24224 KB Output is correct
12 Execution timed out 13058 ms 24224 KB Time limit exceeded
13 Halted 0 ms 0 KB -