oj.uz

답안 #163261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163261 2019-11-12T02:56:47 Z galen_colin 게임 (IOI13_game) C++14
63 / 100
 3364 ms 256000 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;
vector<implicit_segtree> vec(8000000);
int pt = 0;
const int sentinel = 7999999;
struct implicit_segtree {
  bitset<60> v;
  bitset<25> child[2];

  implicit_segtree() {
    v = 0;
    child[0] = sentinel;
    child[1] = sentinel;
  }

  int ch(int x) {
    if (child[x] == sentinel) {
      child[x] = pt++;
    }
    return child[x].to_ulong();
  }

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

  ll add(int loc, ll val, int l, int r) {
    if (l > loc || r < loc) return v.to_ulong();
    if (l == r) return (v = val).to_ulong();
    ll m = (l + r) / 2;
    ll a = 0, b = 0;
    if (loc <= m) {
      a = vec[ch(0)].add(loc, val, l, m);
      if (child[1] != sentinel) b = vec[ch(1)].v.to_ulong();
    } else {
      if (child[0] != sentinel) a = vec[ch(0)].v.to_ulong();
      b = vec[ch(1)].add(loc, val, m + 1, r);
    }
    
    // cout << "add inner " << l << " " << r << " " << a << " " << b << " " << gcd(a, b) << endl;
    return (v = gcd(a, b)).to_ulong();
  }

  ll query(int ql, int qr) {
    return query(ql, qr, 0, m - 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.to_ulong() << endl;
    if (ql <= tl && tr <= qr) return v.to_ulong();
    ll a = 0, b = 0;
    ll m = (tl + tr) / 2;
    if (child[0] != sentinel) a = vec[ch(0)].query(ql, qr, tl, m);
    if (child[1] != sentinel) b = vec[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 {
  implicit_segtree* v;
  implicit_segtree_lv2* child[2];

  implicit_segtree_lv2() {
    v = new implicit_segtree();
    child[0] = nullptr;
    child[1] = nullptr;
  }

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

  void add(int loc, int loc2, ll val) {
    add(loc, loc2, val, 0, n - 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;
    if (loc <= m) {
      a = ch(0)->add(loc, loc2, val, l, m);
      if (child[1]) b = ch(1)->v->query(loc2, loc2);
    } else {
      if (child[0]) a = ch(0)->v->query(loc2, loc2);
      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;
}

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;
//     // cout << "QUERY   __ " << i << " __" << endl;
//     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 161 ms 188280 KB Output is correct
2 Correct 175 ms 188180 KB Output is correct
3 Correct 153 ms 188252 KB Output is correct
4 Correct 172 ms 188280 KB Output is correct
5 Correct 171 ms 188124 KB Output is correct
6 Correct 172 ms 188268 KB Output is correct
7 Correct 174 ms 188152 KB Output is correct
8 Correct 173 ms 188152 KB Output is correct
9 Correct 175 ms 188140 KB Output is correct
10 Correct 174 ms 188224 KB Output is correct
11 Correct 173 ms 188156 KB Output is correct
12 Correct 172 ms 188352 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 188188 KB Output is correct
2 Correct 169 ms 188208 KB Output is correct
3 Correct 169 ms 188232 KB Output is correct
4 Correct 1012 ms 194120 KB Output is correct
5 Correct 774 ms 194252 KB Output is correct
6 Correct 867 ms 191092 KB Output is correct
7 Correct 941 ms 190740 KB Output is correct
8 Correct 662 ms 191528 KB Output is correct
9 Correct 952 ms 190856 KB Output is correct
10 Correct 910 ms 190420 KB Output is correct
11 Correct 154 ms 188152 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 188168 KB Output is correct
2 Correct 156 ms 188236 KB Output is correct
3 Correct 155 ms 188152 KB Output is correct
4 Correct 172 ms 188300 KB Output is correct
5 Correct 172 ms 188232 KB Output is correct
6 Correct 173 ms 188252 KB Output is correct
7 Correct 172 ms 188252 KB Output is correct
8 Correct 173 ms 188152 KB Output is correct
9 Correct 162 ms 188280 KB Output is correct
10 Correct 174 ms 188204 KB Output is correct
11 Correct 154 ms 188280 KB Output is correct
12 Correct 1652 ms 194052 KB Output is correct
13 Correct 3008 ms 191052 KB Output is correct
14 Correct 508 ms 190556 KB Output is correct
15 Correct 3364 ms 191104 KB Output is correct
16 Correct 415 ms 190892 KB Output is correct
17 Correct 1394 ms 191536 KB Output is correct
18 Correct 2248 ms 191308 KB Output is correct
19 Correct 1978 ms 191224 KB Output is correct
20 Correct 1913 ms 190440 KB Output is correct
21 Correct 153 ms 188280 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 188236 KB Output is correct
2 Correct 153 ms 188148 KB Output is correct
3 Correct 155 ms 188204 KB Output is correct
4 Correct 156 ms 188176 KB Output is correct
5 Correct 154 ms 188280 KB Output is correct
6 Correct 154 ms 188188 KB Output is correct
7 Correct 160 ms 188180 KB Output is correct
8 Correct 155 ms 188252 KB Output is correct
9 Correct 160 ms 188324 KB Output is correct
10 Correct 154 ms 188152 KB Output is correct
11 Correct 154 ms 188132 KB Output is correct
12 Correct 998 ms 193532 KB Output is correct
13 Correct 837 ms 193600 KB Output is correct
14 Correct 856 ms 190840 KB Output is correct
15 Correct 1102 ms 190392 KB Output is correct
16 Correct 763 ms 190980 KB Output is correct
17 Correct 917 ms 190152 KB Output is correct
18 Correct 905 ms 189904 KB Output is correct
19 Correct 1647 ms 193392 KB Output is correct
20 Correct 2890 ms 189948 KB Output is correct
21 Correct 499 ms 189660 KB Output is correct
22 Correct 3336 ms 190472 KB Output is correct
23 Correct 413 ms 190456 KB Output is correct
24 Correct 1389 ms 190876 KB Output is correct
25 Correct 2250 ms 190884 KB Output is correct
26 Correct 2268 ms 190616 KB Output is correct
27 Correct 1817 ms 189952 KB Output is correct
28 Correct 921 ms 201100 KB Output is correct
29 Runtime error 2591 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 188244 KB Output is correct
2 Correct 152 ms 188152 KB Output is correct
3 Correct 212 ms 188380 KB Output is correct
4 Correct 151 ms 188128 KB Output is correct
5 Correct 153 ms 188176 KB Output is correct
6 Correct 153 ms 188280 KB Output is correct
7 Correct 157 ms 188280 KB Output is correct
8 Correct 153 ms 188152 KB Output is correct
9 Correct 151 ms 188212 KB Output is correct
10 Correct 154 ms 188152 KB Output is correct
11 Correct 157 ms 188156 KB Output is correct
12 Correct 1010 ms 193316 KB Output is correct
13 Correct 774 ms 193400 KB Output is correct
14 Correct 860 ms 190628 KB Output is correct
15 Correct 934 ms 190236 KB Output is correct
16 Correct 655 ms 190820 KB Output is correct
17 Correct 945 ms 190536 KB Output is correct
18 Correct 867 ms 189944 KB Output is correct
19 Correct 1632 ms 193840 KB Output is correct
20 Correct 2984 ms 190444 KB Output is correct
21 Correct 497 ms 190072 KB Output is correct
22 Correct 3363 ms 190576 KB Output is correct
23 Correct 417 ms 190484 KB Output is correct
24 Correct 1434 ms 190940 KB Output is correct
25 Correct 2296 ms 190556 KB Output is correct
26 Correct 1908 ms 190852 KB Output is correct
27 Correct 1856 ms 190072 KB Output is correct
28 Correct 947 ms 200824 KB Output is correct
29 Runtime error 2592 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -