oj.uz

Submission #110249

# Submission time Handle Problem Language Result Execution time Memory
110249 2019-05-10T10:08:28 Z arnold518 Game (IOI13_game) C++14
63 / 100
 3137 ms 257024 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int r, c;

struct Node1
{
    Node1() : val(0), lc(NULL), rc(NULL) {}
    ll val; Node1 *lc, *rc;
};

struct Node2
{
    Node2() : val(NULL), lc(NULL), rc(NULL) {}
    Node1 *val; Node2 *lc, *rc;
};

Node2 *root;

void init(int R, int C)
{
    r=R; c=C;
    root=new Node2();
}

void update1(Node1* node, int tl, int tr, int x, ll val)
{
    if(tl==tr) { node->val=val; return; }
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x, val);
    }
    node->val=0;
    if(node->lc!=NULL) node->val=__gcd(node->val, node->lc->val);
    if(node->rc!=NULL) node->val=__gcd(node->val, node->rc->val);
}

ll query1(Node1* node, int tl, int tr, int lx, int rx)
{
    if(tr<lx || rx<tl) return 0;
    if(lx<=tl && tr<=rx) return node->val;
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query1(node->lc, tl, mid, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query1(node->rc, mid+1, tr, lx, rx));
    return ret;
}

void update2(Node2* node, int tl, int tr, int y, int x, ll val)
{
    if(node->val==NULL) node->val=new Node1();
    if(tl==tr) { update1(node->val, 1, c, x, val); return; }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x, val);
    }
    ll t=0;
    if(node->lc!=NULL) t=__gcd(t, query1(node->lc->val, 1, c, x, x));
    if(node->rc!=NULL) t=__gcd(t, query1(node->rc->val, 1, c, x, x));
    update1(node->val, 1, c, x, t);
}

ll query2(Node2 *node, int tl, int tr, int ly, int ry, int lx, int rx)
{
    if(tr<ly || ry<tl) return 0;
    if(ly<=tl && tr<=ry && node->val!=NULL) return query1(node->val, 1, c, lx, rx);
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query2(node->lc, tl, mid, ly, ry, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query2(node->rc, mid+1, tr, ly, ry, lx, rx));
    return ret;
}

void update(int P, int Q, ll K)
{
    P++; Q++;
    update2(root, 1, r, P, Q, K);
}

ll calculate(int P, int Q, int U, int V)
{
    P++; Q++; U++; V++;
    return query2(root, 1, r, 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;
      ^~~
game.cpp: In function 'void update1(Node1*, int, int, int, ll)':
game.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(Node1*, int, int, int, int)':
game.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(Node2*, int, int, int, int, ll)':
game.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(Node2*, int, int, int, int, int, int)':
game.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 2 ms 256 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 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 786 ms 17028 KB Output is correct
5 Correct 571 ms 16912 KB Output is correct
6 Correct 897 ms 14712 KB Output is correct
7 Correct 890 ms 14328 KB Output is correct
8 Correct 600 ms 11032 KB Output is correct
9 Correct 1071 ms 14620 KB Output is correct
10 Correct 941 ms 14096 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1603 ms 20108 KB Output is correct
13 Correct 2823 ms 10148 KB Output is correct
14 Correct 409 ms 5752 KB Output is correct
15 Correct 3066 ms 13180 KB Output is correct
16 Correct 325 ms 22520 KB Output is correct
17 Correct 1462 ms 16576 KB Output is correct
18 Correct 2735 ms 24044 KB Output is correct
19 Correct 2203 ms 24212 KB Output is correct
20 Correct 2292 ms 23520 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 9 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 863 ms 16988 KB Output is correct
13 Correct 524 ms 16908 KB Output is correct
14 Correct 740 ms 14740 KB Output is correct
15 Correct 813 ms 14328 KB Output is correct
16 Correct 529 ms 11000 KB Output is correct
17 Correct 896 ms 14456 KB Output is correct
18 Correct 789 ms 14200 KB Output is correct
19 Correct 1357 ms 20088 KB Output is correct
20 Correct 2905 ms 10428 KB Output is correct
21 Correct 484 ms 5780 KB Output is correct
22 Correct 3133 ms 13268 KB Output is correct
23 Correct 307 ms 22468 KB Output is correct
24 Correct 1605 ms 16504 KB Output is correct
25 Correct 3137 ms 23924 KB Output is correct
26 Correct 2448 ms 24184 KB Output is correct
27 Correct 2299 ms 23580 KB Output is correct
28 Runtime error 1330 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 966 ms 16956 KB Output is correct
13 Correct 690 ms 17028 KB Output is correct
14 Correct 933 ms 14688 KB Output is correct
15 Correct 940 ms 14384 KB Output is correct
16 Correct 577 ms 10972 KB Output is correct
17 Correct 950 ms 14536 KB Output is correct
18 Correct 905 ms 14200 KB Output is correct
19 Correct 1389 ms 19960 KB Output is correct
20 Correct 2680 ms 10360 KB Output is correct
21 Correct 338 ms 5624 KB Output is correct
22 Correct 3116 ms 13204 KB Output is correct
23 Correct 294 ms 22520 KB Output is correct
24 Correct 1398 ms 16560 KB Output is correct
25 Correct 2781 ms 24172 KB Output is correct
26 Correct 2622 ms 24084 KB Output is correct
27 Correct 2409 ms 23628 KB Output is correct
28 Runtime error 1667 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -