oj.uz

Submission #65385

# Submission time Handle Problem Language Result Execution time Memory
65385 2018-08-07T13:28:27 Z boook Game (IOI13_game) C++14
0 / 100
 4 ms 616 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
//------------------------------------------------------------
#include "game.h"
#define MAX 23000
#define INF 0x3f3f3f3f
#define mid (l + r >> 1)

long long _gcd(long long a , long long b){
    if(a == 0 || b == 0) return a == 0 ? b : a;
    else return __gcd(a , b); 
}

long long n , m;
long long sum[MAX * 40];
int ls[MAX * 40] , rs[MAX * 40] , sec[MAX * 40] , pos = 2;

void init(int R, int C) {
    n = R , m = C;
}
void update2(int now , int l , int r , int y , long long val){
    if(l == r) return sum[now] = val , void();
    else {
        if(y <= mid + 0){
            if(ls[now] == 0) ls[now] = pos ++;
            update2(ls[now] , l , mid + 0 , y , val);
        }
        if(mid + 1 <= y){
            if(rs[now] == 0) rs[now] = pos ++;
            update2(rs[now] , mid + 1 , r , y , val);
        }
        sum[now] = _gcd(sum[ls[now]] , sum[rs[now]]);
    }
    // DB4("now = " , sum[now] , sum[ls[now]] , sum[rs[now]]);
}
void update1(int now , int l , int r , int x , int y , long long val){
    if(sec[now] == 0) sec[now] = pos ++;
    update2(sec[now] , 0 , m , y , val);
    if(l == r);
    else {
        if(x <= mid + 0){
            if(ls[now] == 0) ls[now] = pos ++;
            update1(ls[now] , l , mid + 0 , x , y , val);
        }
        if(mid + 1 <= x){
            if(rs[now] == 0) rs[now] = pos ++;
            update1(rs[now] , mid + 1 , r , x , y , val);
        }
    }
    
}
void update(int P, int Q, long long K) {
    update1(1 , 0 , n , P , Q , K);
}
long long query2(int now , int l , int r , int ql , int qr){
    // DBGG("now = " , now);
    if(now == 0) return 0;
    if(ql <= l && r <= qr) return sum[now];
    else if(qr <= mid + 0) return query2(ls[now] , l , mid + 0 , ql , qr);
    else if(mid + 1 <= ql) return query2(rs[now] , mid + 1 , r , ql , qr);
    else _gcd(query2(ls[now] , l , mid + 0 , ql , qr) , query2(rs[now] , mid + 1 , r , ql , qr));
}
long long query1(int now , int l , int r , int ql , int qr , int c , int d){
    if(now == 0) return 0;
    if(ql <= l && r <= qr) return query2(sec[now] , 0 , m , c , d);
    else if(qr <= mid + 0) return query1(ls[now] , l , mid + 0 , ql , qr , c , d);
    else if(mid + 1 <= ql) return query1(rs[now] , mid + 1 , r , ql , qr , c , d);
    return _gcd(query1(ls[now] , l , mid + 0 , ql , qr , c , d)
              , query1(rs[now] , mid + 1 , r , ql , qr , c , d));
}
long long calculate(int P, int Q, int U, int V) {
    // DB4(P , Q , U , V);
    // return 42;
    return query1(1 , 0 , n , 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 update2(int, int, int, int, long long int)':
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:39:17: note: in expansion of macro 'mid'
         if(y <= mid + 0){
                 ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:41:35: note: in expansion of macro 'mid'
             update2(ls[now] , l , mid + 0 , y , val);
                                   ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:43:12: note: in expansion of macro 'mid'
         if(mid + 1 <= y){
            ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:45:31: note: in expansion of macro 'mid'
             update2(rs[now] , mid + 1 , r , y , val);
                               ^~~
game.cpp: In function 'void update1(int, int, int, int, int, long long int)':
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:56:17: note: in expansion of macro 'mid'
         if(x <= mid + 0){
                 ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:58:35: note: in expansion of macro 'mid'
             update1(ls[now] , l , mid + 0 , x , y , val);
                                   ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:60:12: note: in expansion of macro 'mid'
         if(mid + 1 <= x){
            ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:62:31: note: in expansion of macro 'mid'
             update1(rs[now] , mid + 1 , r , x , y , val);
                               ^~~
game.cpp: In function 'long long int query2(int, int, int, int, int)':
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:74:19: note: in expansion of macro 'mid'
     else if(qr <= mid + 0) return query2(ls[now] , l , mid + 0 , ql , qr);
                   ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:74:56: note: in expansion of macro 'mid'
     else if(qr <= mid + 0) return query2(ls[now] , l , mid + 0 , ql , qr);
                                                        ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:75:13: note: in expansion of macro 'mid'
     else if(mid + 1 <= ql) return query2(rs[now] , mid + 1 , r , ql , qr);
             ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:75:52: note: in expansion of macro 'mid'
     else if(mid + 1 <= ql) return query2(rs[now] , mid + 1 , r , ql , qr);
                                                    ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:76:36: note: in expansion of macro 'mid'
     else _gcd(query2(ls[now] , l , mid + 0 , ql , qr) , query2(rs[now] , mid + 1 , r , ql , qr));
                                    ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:76:74: note: in expansion of macro 'mid'
     else _gcd(query2(ls[now] , l , mid + 0 , ql , qr) , query2(rs[now] , mid + 1 , r , ql , qr));
                                                                          ^~~
game.cpp: In function 'long long int query1(int, int, int, int, int, int, int)':
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:81:19: note: in expansion of macro 'mid'
     else if(qr <= mid + 0) return query1(ls[now] , l , mid + 0 , ql , qr , c , d);
                   ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:81:56: note: in expansion of macro 'mid'
     else if(qr <= mid + 0) return query1(ls[now] , l , mid + 0 , ql , qr , c , d);
                                                        ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:82:13: note: in expansion of macro 'mid'
     else if(mid + 1 <= ql) return query1(rs[now] , mid + 1 , r , ql , qr , c , d);
             ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:82:52: note: in expansion of macro 'mid'
     else if(mid + 1 <= ql) return query1(rs[now] , mid + 1 , r , ql , qr , c , d);
                                                    ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:83:38: note: in expansion of macro 'mid'
     return _gcd(query1(ls[now] , l , mid + 0 , ql , qr , c , d)
                                      ^~~
game.cpp:22:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l + r >> 1)
              ~~^~~
game.cpp:84:34: note: in expansion of macro 'mid'
               , query1(rs[now] , mid + 1 , r , ql , qr , c , d));
                                  ^~~
game.cpp: In function 'long long int query2(int, int, int, int, int)':
game.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 4 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 616 KB Output is correct
2 Incorrect 3 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 616 KB Output is correct
2 Incorrect 4 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 616 KB Output is correct
2 Incorrect 4 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Incorrect 3 ms 616 KB Output isn't correct
3 Halted 0 ms 0 KB -