oj.uz

Submission #120060

# Submission time Handle Problem Language Result Execution time Memory
120060 2019-06-23T07:13:12 Z nvmdava Game (IOI13_game) C++17
63 / 100
 8036 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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;
}
#define N 1073741824
unordered_map<int, unordered_map<int, long long> > tree;

void init(int R, int C){};

long long get(unordered_map<int, long long>& pnt, int key){
   auto it = pnt.find(key);
   if(it == pnt.end()) return 0;
   return it -> second;
}

void update(int P, int Q, long long K) {
   int idx = P + N;
   int idy = Q + N;
   int t = idy >> 1;
   auto& pntr = tree[idx];
   pntr[idy] = K;
   while(t){
      pntr[t] = gcd2(get(pntr, t << 1), get(pntr, t << 1 | 1));
      t >>= 1;
   }

   idx >>= 1;
   while(idx){
      t = idy >> 1;
      auto& pntrr = tree[idx];
      pntrr[idy] = gcd2(get(tree[idx << 1], idy), get(tree[idx << 1 | 1], idy));
      while(t){
         pntrr[t] = gcd2(get(pntrr, t << 1), get(pntrr, t << 1 | 1));
         t >>= 1;
      }
      idx >>= 1;
   }
}

long long solve(unordered_map<int, long long>& pntr, int id, int l, int r, int L, int R){
   if(l > R || r < L) return 0;
   if(l >= L && r <= R){
      return get(pntr, id);
   }
   int m =(l + r) >> 1;
   return gcd2(solve(pntr, id << 1, l, m, L, R), solve(pntr, id << 1 | 1, m + 1, r, L, R));
}

long long solve(int id, int l, int r, int L, int R, int U, int V){
   if(l > R || r < L) return 0;
   if(l >= L && r <= R){
      return solve(tree[id], 1, 1, N, U, V);
   }
   int m = (l + r) >> 1;
   return gcd2(solve(id << 1, l, m, L, R, U, V), solve(id << 1 | 1, m + 1, r, L, R, U, V));
}

long long calculate(int P, int Q, int U, int V){
   return solve(1, 1, N, 1 + P, 1 + U, 1 + Q, 1 + V);
}

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 4 ms 384 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 8 ms 768 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4319 ms 64420 KB Output is correct
5 Correct 3494 ms 64592 KB Output is correct
6 Correct 4686 ms 62508 KB Output is correct
7 Correct 4533 ms 62308 KB Output is correct
8 Correct 2700 ms 43700 KB Output is correct
9 Correct 4713 ms 62436 KB Output is correct
10 Correct 4061 ms 62036 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 10 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 9 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4676 ms 24456 KB Output is correct
13 Correct 5458 ms 12556 KB Output is correct
14 Correct 2271 ms 1872 KB Output is correct
15 Correct 6166 ms 18824 KB Output is correct
16 Correct 2227 ms 32340 KB Output is correct
17 Correct 4749 ms 22596 KB Output is correct
18 Correct 7501 ms 32560 KB Output is correct
19 Correct 7024 ms 32812 KB Output is correct
20 Correct 6603 ms 31968 KB Output is correct
21 Correct 3 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 11 ms 896 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 9 ms 896 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 4408 ms 64340 KB Output is correct
13 Correct 3740 ms 64812 KB Output is correct
14 Correct 5005 ms 62352 KB Output is correct
15 Correct 4834 ms 62176 KB Output is correct
16 Correct 2817 ms 43308 KB Output is correct
17 Correct 4765 ms 62356 KB Output is correct
18 Correct 4508 ms 61768 KB Output is correct
19 Correct 4700 ms 24176 KB Output is correct
20 Correct 5446 ms 12312 KB Output is correct
21 Correct 2156 ms 1796 KB Output is correct
22 Correct 6230 ms 18616 KB Output is correct
23 Correct 2211 ms 32268 KB Output is correct
24 Correct 5323 ms 22372 KB Output is correct
25 Correct 8036 ms 32460 KB Output is correct
26 Correct 7310 ms 32584 KB Output is correct
27 Correct 7009 ms 31976 KB Output is correct
28 Runtime error 5664 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 9 ms 868 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4422 ms 64328 KB Output is correct
13 Correct 3433 ms 64740 KB Output is correct
14 Correct 4896 ms 62264 KB Output is correct
15 Correct 4406 ms 62056 KB Output is correct
16 Correct 2649 ms 43420 KB Output is correct
17 Correct 4648 ms 62256 KB Output is correct
18 Correct 4268 ms 61828 KB Output is correct
19 Correct 4895 ms 24260 KB Output is correct
20 Correct 6050 ms 12536 KB Output is correct
21 Correct 2254 ms 1792 KB Output is correct
22 Correct 6616 ms 18556 KB Output is correct
23 Correct 2340 ms 32092 KB Output is correct
24 Correct 5241 ms 22300 KB Output is correct
25 Correct 8016 ms 32468 KB Output is correct
26 Correct 7237 ms 32616 KB Output is correct
27 Correct 7051 ms 31960 KB Output is correct
28 Runtime error 5814 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -