oj.uz

Submission #141716

# Submission time Handle Problem Language Result Execution time Memory
141716 2019-08-09T00:49:20 Z crackersamdjam Game (IOI13_game) C++14
80 / 100
 13000 ms 56040 KB 
#include "game.h"
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

typedef long long ll;

#define min(x, y) (x) < (y) ? (x) : (y)

ll algo_gcd(ll gcd_a, ll gcd_b){return gcd_b == 0 ? gcd_a : algo_gcd(gcd_b, gcd_a % gcd_b);}

struct tnode{
    int key, pr;
    ll val, gcd;
    tnode *l, *r;
    tnode(int key, ll val){
        this->key = key;
        this->val = this->gcd = val;
        pr = rand();
        l = r = nullptr;
    }
};

inline void upd(tnode *rt){
    if(rt)
        rt->gcd = algo_gcd(rt->l ? rt->l->gcd : 0, algo_gcd(rt->val, rt->r ? rt->r->gcd : 0));
}

void split(tnode *cur, int key, tnode *&l, tnode *&r){
    if(!cur){
        l = r = nullptr;
        return;
    }
    if(cur->key > key){
        split(cur->l, key, l, cur->l);
        r = cur;
    }
    else{
        split(cur->r, key, cur->r, r);
        l = cur;
    }
    upd(cur);
}

void merge(tnode *&cur, tnode *l, tnode *r){
    if(!l || !r)
        cur = l ? l : r;
    else if(l->pr > r->pr){
        merge(l->r, l->r, r);
        cur = l;
    }
    else{
        merge(r->l, l, r->l);
        cur = r;
    }
    upd(cur);
}

void insert(tnode *&cur, tnode *tnode, bool russian){
    if(!cur)
        cur = tnode;
    else if(cur->key == tnode->key)
        cur->val = tnode->val;
    else if(!russian && cur->pr > tnode->pr){
        split(cur, tnode->key, tnode->l, tnode->r);
        cur = tnode;
    }
    else
        insert(tnode->key < cur->key? cur->l : cur->r, tnode, russian);
    upd(cur->l);
    upd(cur->r);
    upd(cur);
}

bool exist(tnode *cur, int k){
    if(!cur)
        return 0;
    if(cur->key == k)
        return 1;
    if(cur->key > k)
        return exist(cur->l, k);
    return exist(cur->r, k);
}

ll index(tnode *cur, int k){
    if(!cur)
        return 0;
    if(cur->key == k)
        return cur->val;
    if(cur->key > k)
        return index(cur->l, k);
    return index(cur->r, k);
}

struct node{
    node *l, *r;
    tnode *rt;
    
    void update(int nl, int nr, int i, int j, ll v){
        
        if(nl == nr){
            insert(rt, new tnode(j, v), exist(rt, j));
            return;
        }
        
        int nm = (nl+nr)/2;
        
        if(i <= nm){
            if(!l) l = new node();
            l->update(nl, nm, i, j, v);
        }
        else{
            if(!r) r = new node();
            r->update(nm+1, nr, i, j, v);
        }
        if(rt)
            insert(rt, new tnode(j, algo_gcd(l ? index(l->rt, j) : 0, r ? index(r->rt, j) : 0)), exist(rt, j));
        else
            insert(rt, new tnode(j, v), 0);
    }
    
    ll query(int nl, int nr, int lx, int rx, int ly, int ry){
    
        if(rx < nl || lx > nr)
            return 0;
    
        if(lx <= nl && nr <= rx){
            tnode *a, *b, *c;
            split(rt, ly-1, a, b);
            split(b, ry, b, c);
            ll ret = b ? b->gcd : 0;
            merge(b, b, c);
            merge(rt, a, b);
            return ret;
        }
        
        int nm = (nl+nr)/2;
        return algo_gcd(l? l->query(nl, nm, lx, rx, ly, ry) : 0, r? r->query(nm+1, nr, lx, rx, ly, ry) : 0);
    }
    
} segrt;

int n, m;

void init(int r, int c){
    n = r, m = c;
}

void update(int i, int j, ll k){
    segrt.update(0, n-1, i, j, k);
}

ll calculate(int lx, int ly, int rx, int ry){
    return segrt.query(0, n-1, lx, rx, ly, ry);
}

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1675 ms 9760 KB Output is correct
5 Correct 641 ms 9948 KB Output is correct
6 Correct 2852 ms 6676 KB Output is correct
7 Correct 2939 ms 6340 KB Output is correct
8 Correct 2045 ms 6136 KB Output is correct
9 Correct 3007 ms 6608 KB Output is correct
10 Correct 2902 ms 6208 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2404 ms 12860 KB Output is correct
13 Correct 5234 ms 9416 KB Output is correct
14 Correct 812 ms 9568 KB Output is correct
15 Correct 6023 ms 10116 KB Output is correct
16 Correct 573 ms 10004 KB Output is correct
17 Correct 4553 ms 7688 KB Output is correct
18 Correct 7699 ms 10528 KB Output is correct
19 Correct 6694 ms 10628 KB Output is correct
20 Correct 7641 ms 9884 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1652 ms 9772 KB Output is correct
13 Correct 636 ms 9940 KB Output is correct
14 Correct 2824 ms 6640 KB Output is correct
15 Correct 2889 ms 6456 KB Output is correct
16 Correct 2039 ms 6056 KB Output is correct
17 Correct 2938 ms 6512 KB Output is correct
18 Correct 2882 ms 6136 KB Output is correct
19 Correct 2469 ms 12788 KB Output is correct
20 Correct 5191 ms 9604 KB Output is correct
21 Correct 819 ms 9652 KB Output is correct
22 Correct 5995 ms 10060 KB Output is correct
23 Correct 575 ms 9940 KB Output is correct
24 Correct 4549 ms 7720 KB Output is correct
25 Correct 7631 ms 10288 KB Output is correct
26 Correct 6653 ms 10608 KB Output is correct
27 Correct 7634 ms 9860 KB Output is correct
28 Correct 2184 ms 26948 KB Output is correct
29 Correct 3554 ms 29912 KB Output is correct
30 Correct 8344 ms 21576 KB Output is correct
31 Correct 7087 ms 21160 KB Output is correct
32 Correct 1033 ms 21340 KB Output is correct
33 Correct 1858 ms 21616 KB Output is correct
34 Correct 874 ms 24252 KB Output is correct
35 Correct 4895 ms 17904 KB Output is correct
36 Correct 9255 ms 27224 KB Output is correct
37 Correct 7540 ms 27144 KB Output is correct
38 Correct 9197 ms 26596 KB Output is correct
39 Correct 6468 ms 22636 KB Output is correct
40 Correct 2 ms 504 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 368 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1723 ms 9096 KB Output is correct
13 Correct 637 ms 9460 KB Output is correct
14 Correct 2872 ms 6300 KB Output is correct
15 Correct 2955 ms 6140 KB Output is correct
16 Correct 2068 ms 5792 KB Output is correct
17 Correct 2889 ms 5852 KB Output is correct
18 Correct 2856 ms 5752 KB Output is correct
19 Correct 2423 ms 12208 KB Output is correct
20 Correct 5209 ms 8920 KB Output is correct
21 Correct 853 ms 8844 KB Output is correct
22 Correct 5932 ms 8692 KB Output is correct
23 Correct 569 ms 8432 KB Output is correct
24 Correct 4528 ms 5924 KB Output is correct
25 Correct 7785 ms 8732 KB Output is correct
26 Correct 6615 ms 9036 KB Output is correct
27 Correct 7582 ms 8340 KB Output is correct
28 Correct 2166 ms 24084 KB Output is correct
29 Correct 3508 ms 27048 KB Output is correct
30 Correct 8167 ms 20544 KB Output is correct
31 Correct 7160 ms 19628 KB Output is correct
32 Correct 1041 ms 18040 KB Output is correct
33 Correct 1847 ms 17984 KB Output is correct
34 Correct 910 ms 23108 KB Output is correct
35 Correct 5024 ms 14004 KB Output is correct
36 Correct 9244 ms 23528 KB Output is correct
37 Correct 7596 ms 23576 KB Output is correct
38 Correct 9094 ms 22920 KB Output is correct
39 Correct 2988 ms 45316 KB Output is correct
40 Correct 5844 ms 47252 KB Output is correct
41 Correct 11942 ms 41444 KB Output is correct
42 Correct 10673 ms 45140 KB Output is correct
43 Correct 1891 ms 51868 KB Output is correct
44 Correct 1416 ms 42608 KB Output is correct
45 Correct 6467 ms 27468 KB Output is correct
46 Correct 12629 ms 56040 KB Output is correct
47 Correct 12805 ms 55848 KB Output is correct
48 Execution timed out 13046 ms 55000 KB Time limit exceeded
49 Halted 0 ms 0 KB -