oj.uz

Submission #120058

# Submission time Handle Problem Language Result Execution time Memory
120058 2019-06-23T07:07:52 Z nvmdava Game (IOI13_game) C++17
63 / 100
 11036 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
map<int, map<int, long long> > tree;

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

long long get(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(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 3 ms 384 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 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 7 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 7 ms 1024 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 6018 ms 99868 KB Output is correct
5 Correct 4396 ms 99696 KB Output is correct
6 Correct 6722 ms 97916 KB Output is correct
7 Correct 5550 ms 97752 KB Output is correct
8 Correct 3807 ms 60064 KB Output is correct
9 Correct 7012 ms 98204 KB Output is correct
10 Correct 6708 ms 97704 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 3 ms 384 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 7 ms 1024 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 6440 ms 36688 KB Output is correct
13 Correct 7358 ms 20748 KB Output is correct
14 Correct 1888 ms 6520 KB Output is correct
15 Correct 8482 ms 30412 KB Output is correct
16 Correct 2172 ms 49648 KB Output is correct
17 Correct 6749 ms 35904 KB Output is correct
18 Correct 10719 ms 51056 KB Output is correct
19 Correct 9747 ms 51192 KB Output is correct
20 Correct 9381 ms 50492 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 3 ms 384 KB Output is correct
2 Correct 10 ms 1004 KB Output is correct
3 Correct 9 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 7 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 8 ms 512 KB Output is correct
9 Correct 7 ms 1024 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5898 ms 100012 KB Output is correct
13 Correct 4450 ms 99688 KB Output is correct
14 Correct 6990 ms 97908 KB Output is correct
15 Correct 5818 ms 97696 KB Output is correct
16 Correct 3740 ms 59872 KB Output is correct
17 Correct 6793 ms 98180 KB Output is correct
18 Correct 6773 ms 97528 KB Output is correct
19 Correct 6097 ms 36728 KB Output is correct
20 Correct 7489 ms 20732 KB Output is correct
21 Correct 1889 ms 6388 KB Output is correct
22 Correct 8006 ms 30496 KB Output is correct
23 Correct 2137 ms 49472 KB Output is correct
24 Correct 6163 ms 35688 KB Output is correct
25 Correct 11036 ms 51160 KB Output is correct
26 Correct 10041 ms 51188 KB Output is correct
27 Correct 9471 ms 50508 KB Output is correct
28 Runtime error 5746 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 3 ms 384 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 8 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 7 ms 1024 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5818 ms 99948 KB Output is correct
13 Correct 4062 ms 99636 KB Output is correct
14 Correct 6560 ms 97948 KB Output is correct
15 Correct 5560 ms 97564 KB Output is correct
16 Correct 3578 ms 59968 KB Output is correct
17 Correct 6925 ms 98112 KB Output is correct
18 Correct 6655 ms 97688 KB Output is correct
19 Correct 6508 ms 36716 KB Output is correct
20 Correct 7264 ms 20816 KB Output is correct
21 Correct 1879 ms 6312 KB Output is correct
22 Correct 8653 ms 30168 KB Output is correct
23 Correct 2155 ms 49640 KB Output is correct
24 Correct 6483 ms 35764 KB Output is correct
25 Correct 10598 ms 50968 KB Output is correct
26 Correct 9224 ms 51116 KB Output is correct
27 Correct 9025 ms 50564 KB Output is correct
28 Runtime error 5429 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -