oj.uz

Submission #1014555

# Submission time Handle Problem Language Result Execution time Memory
1014555 2024-07-05T06:46:43 Z huutuan Game (IOI13_game) C++14
37 / 100
 13000 ms 13744 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;

struct Node{
   long long val;
   Node *l;
   Node *r;
   Node (){
      val=0;
      l=nullptr;
      r=nullptr;
   }
};

struct SegmentTree{
   Node *root;
   SegmentTree(){
      root=new Node();
   }
   void update(Node *t, int l, int r, int pos, long long val){
      if (l==r){
         t->val=val;
         return;
      }
      if (!t->l) t->l=new Node();
      if (!t->r) t->r=new Node();
      int mid=(l+r)>>1;
      if (pos<=mid) update(t->l, l, mid, pos, val);
      else update(t->r, mid+1, r, pos, val);
      t->val=gcd2(t->l->val, t->r->val);
   }
   long long get(Node *t, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t->val;
      if (!t->l || !t->r) return 0;
      int mid=(l+r)>>1;
      return gcd2(get(t->l, l, mid, L, R), get(t->r, mid+1, r, L, R));
   }
};

int sz;
SegmentTree st[22000];
map<int, int> mp;

void init(int R, int C) {
   
}

void update(int P, int Q, long long K) {
   ++P; ++Q;
   if (!mp.count(P)){
      mp[P]=sz++;
   }
   int id=mp[P];
   st[id].update(st[id].root, 1, 1e9, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
   ++P; ++Q; ++U; ++V;
   long long ans=0;
   for (auto it=mp.lower_bound(P); it!=mp.end(); ++it){
      if (it->first>U) continue;
      ans=gcd2(ans, st[it->second].get(st[it->second].root, 1, 1e9, Q, V));
   }
   return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 1 ms 1164 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 488 ms 13744 KB Output is correct
5 Correct 294 ms 13396 KB Output is correct
6 Correct 378 ms 11044 KB Output is correct
7 Correct 395 ms 10836 KB Output is correct
8 Correct 326 ms 9420 KB Output is correct
9 Correct 372 ms 11088 KB Output is correct
10 Correct 356 ms 10576 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Execution timed out 13080 ms 8168 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 1116 KB Output is correct
2 Correct 1 ms 1300 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 2 ms 1304 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1300 KB Output is correct
11 Correct 1 ms 1368 KB Output is correct
12 Correct 561 ms 13656 KB Output is correct
13 Correct 307 ms 13396 KB Output is correct
14 Correct 389 ms 11084 KB Output is correct
15 Correct 457 ms 10836 KB Output is correct
16 Correct 305 ms 9164 KB Output is correct
17 Correct 419 ms 10972 KB Output is correct
18 Correct 374 ms 10596 KB Output is correct
19 Execution timed out 13013 ms 7784 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 489 ms 13140 KB Output is correct
13 Correct 314 ms 12860 KB Output is correct
14 Correct 404 ms 8940 KB Output is correct
15 Correct 427 ms 8792 KB Output is correct
16 Correct 295 ms 7504 KB Output is correct
17 Correct 425 ms 8788 KB Output is correct
18 Correct 379 ms 8528 KB Output is correct
19 Execution timed out 13041 ms 7876 KB Time limit exceeded
20 Halted 0 ms 0 KB -