oj.uz

답안 #258781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258781 2020-08-06T14:38:56 Z davi_bart 게임 (IOI13_game) C++14
63 / 100
 2931 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
}
const ll dim=1<<30;
class segment{
  public:
  struct node{
    ll val,left,right;
    node(){
      val=0;
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  ll upd(ll pos,ll l,ll r,ll p,ll v){
    if(l>p || r<p)return s[pos].val;
    if(l==r)return s[pos].val=v;
    if(s[pos].left==-1){
      s[pos].left=s.size();
      s.push_back(def);
    }
    if(s[pos].right==-1){
      s[pos].right=s.size();
      s.push_back(def);
    }
    return s[pos].val=gcd2(upd(s[pos].left,l,(l+r)/2,p,v),upd(s[pos].right,(l+r)/2+1,r,p,v));
  }
  ll query(ll pos,ll l,ll r,ll a,ll b){
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].val;
    }
    ll sx=0,dx=0;
    if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b);
    if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b);
    return gcd2(sx,dx);
  }
};
class segofseg{
  public:
  struct node{
    ll left,right;
    segment k;
    node(){
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  void upd(ll pos,ll l,ll r,ll p,ll q,ll v){
    if(l>p || r<p)return ;
    if(l==r){
      s[pos].k.upd(0,0,dim-1,q,v);
      return;
    }
    ll x=0,y=0;
    if(p<=(l+r)/2){
      if(s[pos].left==-1){
        s[pos].left=s.size();
        s.push_back(def);
      }
      upd(s[pos].left,l,(l+r)/2,p,q,v);
    }else{
      if(s[pos].right==-1){
        s[pos].right=s.size();
        s.push_back(def);
      }
      upd(s[pos].right,(l+r)/2+1,r,p,q,v);
    }

    if(s[pos].left!=-1)x=s[s[pos].left].k.query(0,0,dim-1,q,q);
    if(s[pos].right!=-1)y=s[s[pos].right].k.query(0,0,dim-1,q,q);
    s[pos].k.upd(0,0,dim-1,q,gcd2(x,y));
  }
  ll query(ll pos,ll l,ll r,ll a,ll b,ll x,ll y){
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].k.query(0,0,dim-1,x,y);
    }
    ll sx=0,dx=0;
    if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b,x,y);
    if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b,x,y);
    return gcd2(sx,dx);
  }
}tot;
void init(int R, int C) {
}

void update(int P, int Q, long long K){
  tot.upd(0,0,dim-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
  return tot.query(0,0,dim-1,P,U,Q,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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1138 ms 64936 KB Output is correct
5 Correct 932 ms 64120 KB Output is correct
6 Correct 1135 ms 61892 KB Output is correct
7 Correct 1162 ms 61232 KB Output is correct
8 Correct 752 ms 40360 KB Output is correct
9 Correct 1186 ms 62252 KB Output is correct
10 Correct 1106 ms 61296 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1917 ms 30484 KB Output is correct
13 Correct 2395 ms 16120 KB Output is correct
14 Correct 897 ms 4648 KB Output is correct
15 Correct 2681 ms 23120 KB Output is correct
16 Correct 980 ms 41716 KB Output is correct
17 Correct 1641 ms 29172 KB Output is correct
18 Correct 2488 ms 41872 KB Output is correct
19 Correct 2305 ms 41844 KB Output is correct
20 Correct 2145 ms 41208 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1216 ms 64428 KB Output is correct
13 Correct 966 ms 63788 KB Output is correct
14 Correct 1181 ms 61584 KB Output is correct
15 Correct 1210 ms 61000 KB Output is correct
16 Correct 759 ms 39916 KB Output is correct
17 Correct 1192 ms 62032 KB Output is correct
18 Correct 1200 ms 61284 KB Output is correct
19 Correct 1886 ms 30464 KB Output is correct
20 Correct 2557 ms 16132 KB Output is correct
21 Correct 798 ms 4472 KB Output is correct
22 Correct 2714 ms 23032 KB Output is correct
23 Correct 975 ms 41460 KB Output is correct
24 Correct 1567 ms 28916 KB Output is correct
25 Correct 2587 ms 42220 KB Output is correct
26 Correct 2274 ms 42156 KB Output is correct
27 Correct 2330 ms 41404 KB Output is correct
28 Runtime error 729 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1266 ms 64892 KB Output is correct
13 Correct 1018 ms 63880 KB Output is correct
14 Correct 1263 ms 62116 KB Output is correct
15 Correct 1240 ms 61532 KB Output is correct
16 Correct 821 ms 40512 KB Output is correct
17 Correct 1211 ms 62788 KB Output is correct
18 Correct 1239 ms 61876 KB Output is correct
19 Correct 2001 ms 28920 KB Output is correct
20 Correct 2479 ms 14524 KB Output is correct
21 Correct 875 ms 3068 KB Output is correct
22 Correct 2931 ms 21704 KB Output is correct
23 Correct 1371 ms 39984 KB Output is correct
24 Correct 1698 ms 27496 KB Output is correct
25 Correct 2690 ms 40912 KB Output is correct
26 Correct 2567 ms 40776 KB Output is correct
27 Correct 2326 ms 40112 KB Output is correct
28 Runtime error 713 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -