제출 #427228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427228		arayi	Game (IOI13_game)	C++17	0 / 100	1 ms	204 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
using namespace std;

const int mod = 1e9;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        X %= Y; swap(X, Y);
    }
    return X;
}
int n, m;
vector <int> l, r, e1, e2;
vector <vector<int> > l1, r1, t;
void push1(int nd, int i)
{
    if(l1[nd][i] > l1[nd].size()) l1[nd][i] = l1[nd].size(), l1[nd].ad(mod), r1[nd].ad(mod), t[nd].ad(0);
    if(r1[nd][i] > r1[nd].size()) r1[nd][i] = r1[nd].size(), l1[nd].ad(mod), r1[nd].ad(mod), t[nd].ad(0);
}
void upd1(int c, lli v, int nd, int l = 0, int r = m - 1, int i1 = 0)
{
    if(l > c || r < c) return;
    if(l == r) 
    {
        t[nd][i1] = v;
        return;
    }
    push1(nd, i1);
    int mid = (l + r) / 2;
    upd1(c, v, nd, l, mid, l1[nd][i1]);
    upd1(c, v, nd, mid + 1, r, r1[nd][i1]);
    t[nd][i1] = gcd2(t[nd][l1[nd][i1]], t[nd][r1[nd][i1]]);
}
void push(int i)
{
    if(l[i] > l.size()) l[i] = l.size(), l.ad(mod), r.ad(mod), l1.ad(e1), r1.ad(e1), t.ad(e2);
    if(r[i] > r.size()) r[i] = r.size(), l.ad(mod), r.ad(mod), l1.ad(e1), r1.ad(e1), t.ad(e2);
}
void upd(int r1, int c, lli v, int l = 0, int r = n - 1, int nd = 0)
{
    if(l > r1 || r < r1) return;
    //cout << l << " " << r << endl;
    upd1(c, v, nd);
    if(l==r) return;
    int mid = (l + r) / 2;
    push(nd);
    upd(r1, c, v, l, mid, ::l[nd]);
    upd(r1, c, v, mid + 1, r, ::r[nd]);
}
lli qry1(int l, int r, int nd, int nl = 0, int nr = m - 1, int i1 = 0)
{
    if(l > nr || r < nl || i1 == mod) return 0;
    if(l == nl && r == nr) return t[nd][i1];
    int mid = (nl + nr) / 2;
    return gcd2(qry1(l, min(mid, r), nd, nl, mid, l1[nd][i1]), 
        qry1(max(mid + 1, l), r, nd, mid + 1, nr, r1[nd][i1]));
}
lli qry(int l, int r, int l1, int r1, int nl = 0, int nr = n - 1, int nd = 0)
{
    if(l > nr || r < nl || nd == mod) return 0;
    if(l == nl && r == nr) return qry1(l1, r1, nd);
    int mid = (nl + nr) / 2;
    return gcd2(qry(l, min(mid, r), l1, r1, nl, mid, ::l[nd]),
        qry(max(mid + 1, l), r, l1, r1, mid + 1, nr, ::r[nd]));
}
void init(int R, int C) 
{
    n = R, m = C;
    e1.ad(mod), e2.ad(0);
    l.ad(mod), r.ad(mod);
    l1.ad(e1), r1.ad(e1), t.ad(e2);
}

void update(int P, int Q, long long K) 
{
    //cout << P << " " << Q << endl;
    upd(P, Q, K);
    //cout << P << " " << Q << endl;
}

long long calculate(int P, int Q, int U, int V) {
    return qry(P, U, Q, V);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'long long int gcd2(long long int, long long int)':
game.cpp:9:15: warning: unused variable 'tmp' [-Wunused-variable]
    9 |     long long tmp;
      |               ^~~
game.cpp: In function 'void push1(int, int)':
game.cpp:20:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if(l1[nd][i] > l1[nd].size()) l1[nd][i] = l1[nd].size(), l1[nd].ad(mod), r1[nd].ad(mod), t[nd].ad(0);
game.cpp:21:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(r1[nd][i] > r1[nd].size()) r1[nd][i] = r1[nd].size(), l1[nd].ad(mod), r1[nd].ad(mod), t[nd].ad(0);
game.cpp: In function 'void push(int)':
game.cpp:39:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(l[i] > l.size()) l[i] = l.size(), l.ad(mod), r.ad(mod), l1.ad(e1), r1.ad(e1), t.ad(e2);
game.cpp:40:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(r[i] > r.size()) r[i] = r.size(), l.ad(mod), r.ad(mod), l1.ad(e1), r1.ad(e1), t.ad(e2);

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