oj.uz

Submission #1016002

# Submission time Handle Problem Language Result Execution time Memory
1016002 2024-07-07T09:01:55 Z huutuan Game (IOI13_game) C++14
80 / 100
 2248 ms 256000 KB 
#include "game.h"

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;
}

#include <bits/stdc++.h>

using namespace std;

int R, C;

struct Node{
   long long val;
   int il, ir;
   Node (){
      val=0;
      il=0, ir=0;
   }
};

struct SegmentTree{
   vector<Node> t;
   int il, ir;
   SegmentTree(){
      t.emplace_back();
      il=0, ir=0;
   }
};

struct SegmentTree2d{
   vector<SegmentTree> t;
   SegmentTree2d(){
      t.emplace_back();
   }
   void update1(int k, int l, int r, int x, int y, long long val){
      if (l!=r){
         int mid=(l+r)>>1;
         if (x<=mid){
            if (!t[k].il){
               t[k].il=t.size();
               t.emplace_back();
            }
            update1(t[k].il, l, mid, x, y, val);
         }else{
            if (!t[k].ir){
               t[k].ir=t.size();
               t.emplace_back();
            }
            update1(t[k].ir, mid+1, r, x, y, val);
         }
      }
      update2(k, 0, 1, 1e9, y, val, l!=r);
   }
   long long get1(int k, int l, int r, int lx, int rx, int ly, int ry){
      if (rx<l || r<lx) return 0;
      if (lx<=l && r<=rx) return get2(k, 0, 1, 1e9, ly, ry);
      int mid=(l+r)>>1;
      return gcd2(t[k].il?get1(t[k].il, l, mid, lx, rx, ly, ry):0, t[k].ir?get1(t[k].ir, mid+1, r, lx, rx, ly, ry):0);
   }
   void update2(int id, int k, int l, int r, int pos, long long val, bool sussy){
      if (l==r){
         if (sussy) t[id].t[k].val=gcd2(t[id].il?get2(t[id].il, 0, 1, 1e9, pos, pos):0, t[id].ir?get2(t[id].ir, 0, 1, 1e9, pos, pos):0);
         else t[id].t[k].val=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid){
         if (!t[id].t[k].il){
            t[id].t[k].il=t[id].t.size();
            t[id].t.emplace_back();
         }
         update2(id, t[id].t[k].il, l, mid, pos, val, sussy);
      }else{
         if (!t[id].t[k].ir){
            t[id].t[k].ir=t[id].t.size();
            t[id].t.emplace_back();
         }
         update2(id, t[id].t[k].ir, mid+1, r, pos, val, sussy);
      }
      t[id].t[k].val=gcd2(t[id].t[k].il?t[id].t[t[id].t[k].il].val:0, t[id].t[k].ir?t[id].t[t[id].t[k].ir].val:0);
   }
   long long get2(int id, int k, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t[id].t[k].val;
      int mid=(l+r)>>1;
      return gcd2(t[id].t[k].il?get2(id, t[id].t[k].il, l, mid, L, R):0, t[id].t[k].ir?get2(id, t[id].t[k].ir, mid+1, r, L, R):0);
   }
} st;

void init(int _R, int _C) {
   R=_R; C=_C;
}

void update(int P, int Q, long long K) {
   ++P; ++Q;
   st.update1(0, 1, 1e9, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
   ++P; ++Q; ++U; ++V;
   return st.get1(0, 1, 1e9, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 562 ms 33552 KB Output is correct
5 Correct 441 ms 33848 KB Output is correct
6 Correct 516 ms 31040 KB Output is correct
7 Correct 541 ms 30272 KB Output is correct
8 Correct 376 ms 20880 KB Output is correct
9 Correct 515 ms 30536 KB Output is correct
10 Correct 503 ms 30276 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 777 ms 18980 KB Output is correct
13 Correct 936 ms 10576 KB Output is correct
14 Correct 389 ms 5708 KB Output is correct
15 Correct 1042 ms 13804 KB Output is correct
16 Correct 438 ms 21332 KB Output is correct
17 Correct 672 ms 16724 KB Output is correct
18 Correct 958 ms 22608 KB Output is correct
19 Correct 940 ms 22648 KB Output is correct
20 Correct 908 ms 22100 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 562 ms 33572 KB Output is correct
13 Correct 405 ms 33600 KB Output is correct
14 Correct 486 ms 31176 KB Output is correct
15 Correct 530 ms 30264 KB Output is correct
16 Correct 373 ms 20928 KB Output is correct
17 Correct 531 ms 30628 KB Output is correct
18 Correct 508 ms 30376 KB Output is correct
19 Correct 761 ms 18772 KB Output is correct
20 Correct 947 ms 10320 KB Output is correct
21 Correct 405 ms 5720 KB Output is correct
22 Correct 1078 ms 13904 KB Output is correct
23 Correct 417 ms 21268 KB Output is correct
24 Correct 679 ms 16592 KB Output is correct
25 Correct 1028 ms 22604 KB Output is correct
26 Correct 1014 ms 22612 KB Output is correct
27 Correct 912 ms 22008 KB Output is correct
28 Correct 494 ms 156040 KB Output is correct
29 Correct 1121 ms 171172 KB Output is correct
30 Correct 2147 ms 123720 KB Output is correct
31 Correct 2075 ms 101248 KB Output is correct
32 Correct 339 ms 10324 KB Output is correct
33 Correct 427 ms 12620 KB Output is correct
34 Correct 383 ms 165284 KB Output is correct
35 Correct 715 ms 90620 KB Output is correct
36 Correct 1227 ms 169264 KB Output is correct
37 Correct 1054 ms 169384 KB Output is correct
38 Correct 1063 ms 168828 KB Output is correct
39 Correct 957 ms 132804 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 508 ms 33392 KB Output is correct
13 Correct 428 ms 33596 KB Output is correct
14 Correct 534 ms 31188 KB Output is correct
15 Correct 516 ms 30180 KB Output is correct
16 Correct 334 ms 20904 KB Output is correct
17 Correct 498 ms 30524 KB Output is correct
18 Correct 477 ms 30432 KB Output is correct
19 Correct 745 ms 18740 KB Output is correct
20 Correct 949 ms 10580 KB Output is correct
21 Correct 361 ms 5720 KB Output is correct
22 Correct 1057 ms 13852 KB Output is correct
23 Correct 427 ms 21236 KB Output is correct
24 Correct 722 ms 16644 KB Output is correct
25 Correct 997 ms 22860 KB Output is correct
26 Correct 959 ms 22792 KB Output is correct
27 Correct 945 ms 22100 KB Output is correct
28 Correct 500 ms 156048 KB Output is correct
29 Correct 1038 ms 171056 KB Output is correct
30 Correct 2117 ms 123736 KB Output is correct
31 Correct 2248 ms 101036 KB Output is correct
32 Correct 336 ms 10320 KB Output is correct
33 Correct 481 ms 12628 KB Output is correct
34 Correct 407 ms 165288 KB Output is correct
35 Correct 754 ms 90544 KB Output is correct
36 Correct 1211 ms 169128 KB Output is correct
37 Correct 1057 ms 169380 KB Output is correct
38 Correct 1106 ms 168740 KB Output is correct
39 Runtime error 645 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -