oj.uz

답안 #163237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163237 2019-11-12T00:18:13 Z galen_colin 게임 (IOI13_game) C++14
63 / 100
 3232 ms 256004 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
 
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < n; i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const ll mod = 998244353;
 
ll madd(ll a, ll b) {
  return (a + b) % mod;
}
ll msub(ll a, ll b) {
  return (((a - b) % mod) + mod) % mod;
}
ll mmul(ll a, ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
ll mpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp % 2 == 1){
        res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}
ll minv(ll base) {
  return mpow(base, mod - 2);
}
ll mdiv(ll a, ll b) {
  return mmul(a, minv(b));
}
ll gcd(ll x, ll y) {
  if (x == 0) return y;
  if (y == 0) return x;
  return gcd(y, x % y);
}
 
bool prime[1000006]; 
void sieve(int n) { 
  f0r(i, n + 1) prime[i] = 1;
  for (int p = 2; p * p <= n; p++) { 
    if (prime[p] == true) { 
      for (int i = p * p; i <= n; i += p) 
        prime[i] = false; 
    } 
  } 
  prime[1] = prime[0] = 0;
} 
 
ll n, m, k, q, Q, T, l, r, x, y, z;
ll a[500005];
ll b[500005];
string s, t;
ll ans = 0;

using implicit_segtree = struct implicit_segtree;
struct implicit_segtree {
  ll v, sz;
  implicit_segtree* child[2];

  implicit_segtree() {

  }

  implicit_segtree(int n) {
    v = 0;
    child[0] = nullptr;
    child[1] = nullptr;
    sz = n;
  }

  implicit_segtree* ch(int x) {
    if (!child[x]) child[x] = new implicit_segtree(sz);
    return child[x];
  }

  void add(int loc, ll val) {
    add(loc, val, 0, sz - 1);
  }

  ll add(int loc, ll val, int l, int r) {
    if (l > loc || r < loc) return v;
    if (l == r) return v = val;
    ll m = (l + r) / 2;
    ll a = 0, b = 0;
    a = ch(0)->add(loc, val, l, m);
    b = ch(1)->add(loc, val, m + 1, r);
    // cout << "inner " << l << " " << r << " " << a << " " << b << " " << gcd(a, b) << endl;
    return v = gcd(a, b);
  }

  ll query(int ql, int qr) {
    return query(ql, qr, 0, sz - 1);
  }

  ll query(int ql, int qr, int tl, int tr) {
    if (qr < tl || ql > tr || tl > tr) return 0;
    // cout << "inner " << ql << " " << qr << " " << tl << " " << tr << " " << v << endl;
    if (ql <= tl && tr <= qr) return v;
    ll a = 0, b = 0, m = (tl + tr) / 2;
    if (child[0]) a = ch(0)->query(ql, qr, tl, m);
    if (child[1]) b = ch(1)->query(ql, qr, m + 1, tr);
    // cout << tl << " " << tr << " " << a << " " << b << endl;
    return gcd(a, b);
  }
};

using implicit_segtree_lv2 = struct implicit_segtree_lv2;
struct implicit_segtree_lv2 {
  int sz;
  implicit_segtree v;
  implicit_segtree_lv2* child[2];

  implicit_segtree_lv2() {

  }

  implicit_segtree_lv2(int n) {
    v = implicit_segtree(m);
    child[0] = nullptr;
    child[1] = nullptr;
    sz = n;
  }

  implicit_segtree_lv2* ch(int x) {
    if (!child[x]) child[x] = new implicit_segtree_lv2(sz);
    return child[x];
  }

  void add(int loc, int loc2, ll val) {
    add(loc, loc2, val, 0, sz - 1);
  }

  ll add(int loc, int loc2, ll val, int l, int r) {
    // cout << "add outer " << l << " " << r << " " << loc2 << " " << val << endl;
    if (l > loc || r < loc) return v.query(loc2, loc2);
    if (l == r) {
      v.add(loc2, val);
      return val;
    }
    ll m = (l + r) / 2;
    ll a = 0, b = 0;
    a = ch(0)->add(loc, loc2, val, l, m);
    b = ch(1)->add(loc, loc2, val, m + 1, r);
    ll x = gcd(a, b);
    v.add(loc2, x);
    return x;
  }

  ll query(int ql1, int qr1, int ql2, int qr2) {
    return query(ql1, qr1, ql2, qr2, 0, n - 1);
  }

  ll query(int ql1, int qr1, int ql2, int qr2, int tl, int tr) {
    // cout << "outer " << ql1 << " " << qr1 << " " << tl << " " << tr << endl;
    if (qr1 < tl || ql1 > tr || tl > tr) return 0;
    if (ql1 <= tl && tr <= qr1) return v.query(ql2, qr2);
    ll a = 0, b = 0, m = (tl + tr) / 2;
    if (child[0]) a = ch(0)->query(ql1, qr1, ql2, qr2, tl, m);
    if (child[1]) b = ch(1)->query(ql1, qr1, ql2, qr2, m + 1, tr);
    return gcd(a, b);
  }
};

#include "game.h"

implicit_segtree_lv2 st;

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

void update(int r, int c, ll v) {
  st.add(r, c, v);
}

ll calculate(int r1, int c1, int r2, int c2) {
  return st.query(r1, r2, c1, c2);
}

// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   usaco("file");

//   cin >> n >> m >> Q;
//   init(n, m);
//   f0r(i, Q) {
//     cin >> q;
//     if (q == 1) {
//       ll a, b, c; cin >> a >> b >> c;
//       update(a, b, c);
//     } else {
//       ll a, b, c, d; cin >> a >> b >> c >> d;
//       cout << "Q " << a << " " << b << " " << c << " " << d << endl;
//       cout << calculate(a, b, c, d) << endl;
//     }
//   }
// }

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 usaco(std::__cxx11::string)':
game.cpp:54:53: note: #pragma message: be careful, freopen may be wrong
   #pragma message("be careful, freopen may be wrong")
                                                     ^
game.cpp:55:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:56:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 424 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 967 ms 29768 KB Output is correct
5 Correct 759 ms 29560 KB Output is correct
6 Correct 851 ms 27528 KB Output is correct
7 Correct 964 ms 27284 KB Output is correct
8 Correct 599 ms 18652 KB Output is correct
9 Correct 934 ms 27588 KB Output is correct
10 Correct 1010 ms 27100 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 3 ms 632 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 632 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 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1618 ms 35784 KB Output is correct
13 Correct 2719 ms 16464 KB Output is correct
14 Correct 397 ms 5880 KB Output is correct
15 Correct 3229 ms 23424 KB Output is correct
16 Correct 353 ms 47864 KB Output is correct
17 Correct 1559 ms 31620 KB Output is correct
18 Correct 2735 ms 49508 KB Output is correct
19 Correct 2279 ms 49680 KB Output is correct
20 Correct 2302 ms 48816 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 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 632 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 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 934 ms 29800 KB Output is correct
13 Correct 708 ms 29560 KB Output is correct
14 Correct 825 ms 27640 KB Output is correct
15 Correct 954 ms 27256 KB Output is correct
16 Correct 594 ms 18776 KB Output is correct
17 Correct 903 ms 27768 KB Output is correct
18 Correct 828 ms 27052 KB Output is correct
19 Correct 1574 ms 35832 KB Output is correct
20 Correct 2733 ms 16660 KB Output is correct
21 Correct 401 ms 5884 KB Output is correct
22 Correct 3224 ms 23492 KB Output is correct
23 Correct 377 ms 47900 KB Output is correct
24 Correct 1630 ms 31736 KB Output is correct
25 Correct 2821 ms 49460 KB Output is correct
26 Correct 2456 ms 49912 KB Output is correct
27 Correct 2385 ms 48832 KB Output is correct
28 Runtime error 584 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 632 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 504 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 956 ms 29816 KB Output is correct
13 Correct 696 ms 29572 KB Output is correct
14 Correct 874 ms 27540 KB Output is correct
15 Correct 943 ms 27356 KB Output is correct
16 Correct 588 ms 18616 KB Output is correct
17 Correct 936 ms 27508 KB Output is correct
18 Correct 861 ms 27036 KB Output is correct
19 Correct 1602 ms 35796 KB Output is correct
20 Correct 2741 ms 16500 KB Output is correct
21 Correct 398 ms 5884 KB Output is correct
22 Correct 3232 ms 23544 KB Output is correct
23 Correct 370 ms 47968 KB Output is correct
24 Correct 1633 ms 31608 KB Output is correct
25 Correct 2761 ms 49308 KB Output is correct
26 Correct 2389 ms 49704 KB Output is correct
27 Correct 2281 ms 49064 KB Output is correct
28 Runtime error 559 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -