Submission #20212

#	Time	Username	Problem	Language	Result	Execution time	Memory
20212		murat	Game (IOI13_game)	C++98	0 / 100	2 ms	0 KiB

game

#include<bits/stdc++.h>
#include "game.h"

using namespace std;

const int inf = 1e9 + 5;
typedef long long ll;
const int N = 30000;

#define orta ((bas) + (son) >> 1)


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;
}

class node {
    public:
    node *l, *r;
    int x, y, heap, size;
    ll gcd, g;
    node() {
        l = r = NULL;
        size = heap = x = y = gcd = g = 0;
    }
};

typedef node* pnode;

pnode ST[N * 30], t1, t2, t3, t4;
int L[N * 30], R[N * 30], S = 1;

pnode make(int x, int y, ll g) {
    pnode temp = new node;
    temp->heap = rand() * rand();
    temp->g = temp->gcd = g;
    temp->l = temp->r = 0;
    temp->size = 1;
    temp->x = x;
    temp->y = y;
    return temp;
}

void relax(pnode &T) {
    if(!T) return ;
    T->size = 1;
    T->gcd = T->g;
    if(T->l) { T->size += T->l->size; T->gcd = gcd2(T->gcd, T->l->gcd); }
    if(T->r) { T->size += T->r->size; T->gcd = gcd2(T->gcd, T->r->gcd); }
}

void merge(pnode &T, pnode l, pnode r) {
    if(!l) { T = r; return ;}
    if(!r) { T = l; return ;}
    if(l->heap > r->heap) {
        merge(l->r, l->r, r);
        T = l;
    }
    else {
        merge(r->l, l, r->l);
        T = r;
    }
    relax(T);
}

void split(pnode T, pnode &l, pnode &r, int x) {
    if(!T) { l = r = NULL; return ; }
    int s = (T->l) ? T->l->size : 0;
    if(s >= x) {
        split(T->l, l, T->l, x);
        r = T;
    }
    else {
        split(T->r, T->r, r, x - s);
        l = T;
    }
    relax(l); relax(r);
}

int lower_bound(pnode &T, int x, int y) {
    if(!T) return 0;
    if(make_pair(T->y, T->x) == make_pair(y, x)) return (T->l ? (T->l->size) : 0) + 1;
    if(make_pair(T->y, T->x) < make_pair(y, x)) return lower_bound(T->r, x, y) + (T->l ? (T->l->size) : 0) + 1;
    return lower_bound(T->l, x, y);
}

void change(pnode &T, int x, int y, ll g) {
    if(!T) { T = make(x, y, g); return ;}
    int tt = lower_bound(T, x, y);
    split(T, t1, t2, tt);
    split(t1, t3, t4, tt-1);
    if(t4 && t4->x == x && t4->y == y) { t4->g = t4->gcd = g; merge(t1, t3, t4); }
    else { merge(t1, t3, t4); merge(t1, t1, make(x, y, g)); }
    merge(T, t1, t2);
}

void update(int k, int bas, int son, int x, int y, ll g) {
    change(ST[k], x, y, g);
    if(bas == son) return ;
    if(x <= orta) {
        if(!L[k]) { ST[S+1] = make(inf, inf, inf); L[k] = ++S; }
        update(L[k], bas, orta, x, y, g);
    }
    else {
        if(!R[k]) { R[k] = ++S; ST[S] = make(inf, inf, inf); }
        update(R[k], orta + 1, son, x, y, g);
    }
}

void print(pnode T) {
    if(!T) return ;
    print(T->l);
    printf("-> %d %d %lld", T->x, T->y, T->g); cout << endl;
    print(T->r);
}

ll query(int k, int bas, int son, int x, int y, int a, int b) {
    if(!k || bas > y || son < x) return 0;
    if(x <= bas && son <= y) {
        int l = lower_bound(ST[k], 0, a);
        int r = lower_bound(ST[k], 0, b+1) - 1;
        split(ST[k], t1, t2, r);
        split(t1, t3, t4, l-1);
        ll cur = t4->gcd;
        return cur;
    }
    return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
}

void init(int R, int C) {
	srand(time(0));
    ST[1] = make(inf, inf, inf);
}

void update(int P, int Q, long long K) {
    update(1, 0, inf, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(1, 0, inf, P, U, Q, V);
}

Compilation message (stderr)

/root/share/problems/files/104/grader.c: In function 'int main()':
/root/share/problems/files/104/grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
game.cpp: In function 'void update(int, int, int, int, int, ll)':
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define orta ((bas) + (son) >> 1)
                     ^
game.cpp:106:13: note: in expansion of macro 'orta'
     if(x <= orta) {
             ^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define orta ((bas) + (son) >> 1)
                     ^
game.cpp:108:27: note: in expansion of macro 'orta'
         update(L[k], bas, orta, x, y, g);
                           ^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define orta ((bas) + (son) >> 1)
                     ^
game.cpp:112:22: note: in expansion of macro 'orta'
         update(R[k], orta + 1, son, x, y, g);
                      ^
game.cpp: In function 'll query(int, int, int, int, int, int, int)':
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define orta ((bas) + (son) >> 1)
                     ^
game.cpp:133:34: note: in expansion of macro 'orta'
     return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
                                  ^
game.cpp:10:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define orta ((bas) + (son) >> 1)
                     ^
game.cpp:133:65: note: in expansion of macro 'orta'
     return gcd2(query(L[k], bas, orta, x, y, a, b), query(R[k], orta + 1, son, x, y, a, b));
                                                                 ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20