oj.uz

Submission #1014554

# Submission time Handle Problem Language Result Execution time Memory
1014554 2024-07-05T06:45:43 Z huutuan Game (IOI13_game) C++14
0 / 100
 2 ms 1116 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{
   int 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -