oj.uz

Submission #507643

# Submission time Handle Problem Language Result Execution time Memory
507643 2022-01-12T22:02:19 Z sofapuden Game (IOI13_game) C++14
63 / 100
 1805 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

ll gcd2(ll X, ll Y) {
  ll tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

long long mxN = 1<<30;

struct seg1d{

  int lb, rb;
  ll val;

  seg1d *l, *r;

  seg1d () : l(NULL), r(NULL), val(0) {}

  inline void init(int lx, int rx){
    lb = lx, rb = rx;
  }

  inline void exl(){
    int mid = (lb+rb)>>1;
    l = new seg1d;
    l->init(lb,mid);
  }
  inline void exr(){
    int mid = (lb+rb)>>1;
    r = new seg1d;
    r->init(mid+1,rb);
  }

  ll getGCD(int llb, int rrb){
    if(llb > rb || rrb < lb)return 0;
    if(llb <= lb && rrb >= rb)return val;
    if(l == NULL && r == NULL)return 0;
    if(l == NULL)return r->getGCD(llb,rrb);
    if(r == NULL)return l->getGCD(llb,rrb);
    return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
  }

  void ch(int x, ll va){
    if(rb < x || lb > x)return;
    if(rb == x && lb == x){
      val = va;
      return;
    }
    int mid = (lb+rb)>>1;
    if(mid >= x){
      if(l == NULL)exl();
      l->ch(x,va);
      if(r == NULL)val = l->val;
      else val = gcd2(l->val,r->val);
    }
    else{
      if(r == NULL)exr();
      r->ch(x,va);
      if(l == NULL)val = r->val;
      else val = gcd2(l->val,r->val);
    }
  }
  void chno(seg1d *a, seg1d *b, int x){
    if(rb < x || lb > x)return;
    int mid = (lb+rb)>>1;
    if(mid >= x){
      if(a == NULL){
        val = b->val;
        if(rb == lb)return;
        if(l == NULL)exl();
        l->chno(a,b->l,x);
        return;
      }
      if(b == NULL){
        val = a->val;
        if(rb == lb)return;
        if(l == NULL)exl();
        l->chno(a->l,b,x);
        return;
      }
      val = gcd2(a->val,b->val);
      if(rb == lb)return;
      if(l == NULL)exl();
      l->chno(a->l,b->l,x);
    }
    else{
      if(a == NULL){
        val = b->val;
        if(rb == lb)return;
        if(r == NULL)exr();
        r->chno(a,b->r,x);
        return;
      }
      if(b == NULL){
        val = a->val;
        if(rb == lb)return;
        if(r == NULL)exr();
        r->chno(a->r,b,x);
        return;
      }
      val = gcd2(a->val,b->val);
      if(rb == lb)return;
      if(r == NULL)exr();
      r->chno(a->r,b->r,x);
    }
  }
};

struct seg2d{

  int lb, rb;

  seg2d *l, *r;
  seg1d *c;

  seg2d () : l(NULL), r(NULL), c(NULL) {}

  inline void init(int lx, int rx){
    lb = lx, rb = rx;
  }

  inline void exl(){
    int mid = (lb+rb)>>1;
    l = new seg2d;
    l->init(lb,mid);
  }
  inline void exr(){
    int mid = (lb+rb)>>1;
    r = new seg2d;
    r->init(mid+1,rb);
  }
  inline void exc(){
    c = new seg1d;
    c->init(0, mxN);
  }

  ll getGCD(int llb, int rrb, int uub, int ddb){
    if(llb > rb || rrb < lb)return 0;
    if(llb <= lb && rrb >= rb){
      if(c == NULL)return 0;
      return c->getGCD(uub,ddb);
    }
    if((l == NULL && r == NULL) || c == NULL)return 0;
    if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
    if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
    return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
  }

  void ch(int x, int y, ll val){
    if(rb < x || lb > x)return;
    if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
    int mid = (rb+lb)>>1;
    if(mid >= x){
      if(l == NULL)exl();
      if(c == NULL)exc();
      l->ch(x,y,val);
      if(r == NULL){
        exr();
      }
      c->chno(l->c,r->c,y);
    }
    else{
      if(r == NULL)exr();
      if(c == NULL)exc();
      r->ch(x,y,val);
      if(l == NULL){
        exl();
      }
      c->chno(l->c,r->c,y);
    }
  }	
};

seg2d root;

void init(int R, int C) {
  root.init(0,mxN);
}

void update(int P, int Q, long long K) {
  root.ch(P+1,Q+1,K);
}

long long calculate(int P, int Q, int U, int V) {
  return root.getGCD(P+1,U+1,Q+1,V+1);
}

Compilation message

game.cpp: In constructor 'seg1d::seg1d()':
game.cpp:25:14: warning: 'seg1d::r' will be initialized after [-Wreorder]
   25 |   seg1d *l, *r;
      |              ^
game.cpp:23:6: warning:   'll seg1d::val' [-Wreorder]
   23 |   ll val;
      |      ^~~
game.cpp:27:3: warning:   when initialized here [-Wreorder]
   27 |   seg1d () : l(NULL), r(NULL), val(0) {}
      |   ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 0 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 633 ms 73112 KB Output is correct
5 Correct 460 ms 73512 KB Output is correct
6 Correct 674 ms 71012 KB Output is correct
7 Correct 701 ms 70696 KB Output is correct
8 Correct 464 ms 42852 KB Output is correct
9 Correct 710 ms 71100 KB Output is correct
10 Correct 665 ms 70620 KB Output is correct
11 Correct 0 ms 324 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1063 ms 25952 KB Output is correct
13 Correct 1438 ms 13192 KB Output is correct
14 Correct 392 ms 1804 KB Output is correct
15 Correct 1608 ms 19976 KB Output is correct
16 Correct 1217 ms 34768 KB Output is correct
17 Correct 1048 ms 23776 KB Output is correct
18 Correct 1793 ms 35020 KB Output is correct
19 Correct 1578 ms 35016 KB Output is correct
20 Correct 1453 ms 34512 KB Output is correct
21 Correct 1 ms 276 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 614 ms 73176 KB Output is correct
13 Correct 463 ms 73444 KB Output is correct
14 Correct 664 ms 71012 KB Output is correct
15 Correct 700 ms 70860 KB Output is correct
16 Correct 479 ms 43100 KB Output is correct
17 Correct 688 ms 71072 KB Output is correct
18 Correct 653 ms 70576 KB Output is correct
19 Correct 1040 ms 25924 KB Output is correct
20 Correct 1428 ms 13184 KB Output is correct
21 Correct 371 ms 1816 KB Output is correct
22 Correct 1626 ms 19876 KB Output is correct
23 Correct 1204 ms 34536 KB Output is correct
24 Correct 1097 ms 23788 KB Output is correct
25 Correct 1805 ms 34720 KB Output is correct
26 Correct 1515 ms 35236 KB Output is correct
27 Correct 1442 ms 34600 KB Output is correct
28 Runtime error 471 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 2 ms 800 KB Output is correct
3 Correct 2 ms 844 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 284 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 404 KB Output is correct
12 Correct 621 ms 72932 KB Output is correct
13 Correct 454 ms 73292 KB Output is correct
14 Correct 658 ms 70876 KB Output is correct
15 Correct 693 ms 70464 KB Output is correct
16 Correct 475 ms 42572 KB Output is correct
17 Correct 703 ms 70844 KB Output is correct
18 Correct 682 ms 70420 KB Output is correct
19 Correct 1033 ms 25668 KB Output is correct
20 Correct 1431 ms 12984 KB Output is correct
21 Correct 368 ms 1520 KB Output is correct
22 Correct 1608 ms 19664 KB Output is correct
23 Correct 1256 ms 34320 KB Output is correct
24 Correct 1045 ms 23680 KB Output is correct
25 Correct 1733 ms 34568 KB Output is correct
26 Correct 1523 ms 34904 KB Output is correct
27 Correct 1457 ms 34224 KB Output is correct
28 Runtime error 508 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -