답안 #163265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163265	2019-11-12T03:06:40 Z	galen_colin	게임 (IOI13_game)	C++14	80 / 100	6308 ms	256000 KB

game

#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(14000000);
int pt = 0;
const int sentinel = 13999999;
struct implicit_segtree {
  bitset<60> v;
  int 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];
  }

  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	192 ms	219512 KB	Output is correct
2	Correct	186 ms	219540 KB	Output is correct
3	Correct	184 ms	219516 KB	Output is correct
4	Correct	185 ms	219640 KB	Output is correct
5	Correct	183 ms	219544 KB	Output is correct
6	Correct	184 ms	219628 KB	Output is correct
7	Correct	187 ms	219464 KB	Output is correct
8	Correct	186 ms	219460 KB	Output is correct
9	Correct	184 ms	219512 KB	Output is correct
10	Correct	199 ms	219640 KB	Output is correct
11	Correct	184 ms	219508 KB	Output is correct
12	Correct	184 ms	219512 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	204 ms	219640 KB	Output is correct
2	Correct	186 ms	219512 KB	Output is correct
3	Correct	187 ms	219660 KB	Output is correct
4	Correct	1022 ms	223792 KB	Output is correct
5	Correct	822 ms	224224 KB	Output is correct
6	Correct	880 ms	221008 KB	Output is correct
7	Correct	939 ms	220548 KB	Output is correct
8	Correct	692 ms	221596 KB	Output is correct
9	Correct	929 ms	220768 KB	Output is correct
10	Correct	897 ms	220372 KB	Output is correct
11	Correct	204 ms	219492 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	194 ms	219684 KB	Output is correct
2	Correct	184 ms	219512 KB	Output is correct
3	Correct	189 ms	219468 KB	Output is correct
4	Correct	190 ms	219640 KB	Output is correct
5	Correct	209 ms	219484 KB	Output is correct
6	Correct	204 ms	219624 KB	Output is correct
7	Correct	186 ms	219540 KB	Output is correct
8	Correct	185 ms	219512 KB	Output is correct
9	Correct	185 ms	219512 KB	Output is correct
10	Correct	206 ms	219572 KB	Output is correct
11	Correct	190 ms	219536 KB	Output is correct
12	Correct	1639 ms	224212 KB	Output is correct
13	Correct	2845 ms	220908 KB	Output is correct
14	Correct	544 ms	220284 KB	Output is correct
15	Correct	3354 ms	220904 KB	Output is correct
16	Correct	456 ms	220888 KB	Output is correct
17	Correct	1397 ms	221344 KB	Output is correct
18	Correct	2244 ms	221340 KB	Output is correct
19	Correct	1885 ms	221420 KB	Output is correct
20	Correct	1781 ms	220852 KB	Output is correct
21	Correct	193 ms	219616 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	203 ms	219452 KB	Output is correct
2	Correct	207 ms	219640 KB	Output is correct
3	Correct	205 ms	219540 KB	Output is correct
4	Correct	207 ms	219512 KB	Output is correct
5	Correct	206 ms	219648 KB	Output is correct
6	Correct	203 ms	219640 KB	Output is correct
7	Correct	185 ms	219512 KB	Output is correct
8	Correct	188 ms	219648 KB	Output is correct
9	Correct	185 ms	219644 KB	Output is correct
10	Correct	202 ms	219628 KB	Output is correct
11	Correct	189 ms	219516 KB	Output is correct
12	Correct	1018 ms	223960 KB	Output is correct
13	Correct	813 ms	224224 KB	Output is correct
14	Correct	865 ms	220908 KB	Output is correct
15	Correct	941 ms	220772 KB	Output is correct
16	Correct	676 ms	221424 KB	Output is correct
17	Correct	910 ms	220880 KB	Output is correct
18	Correct	954 ms	220412 KB	Output is correct
19	Correct	1621 ms	224140 KB	Output is correct
20	Correct	2947 ms	220736 KB	Output is correct
21	Correct	526 ms	220664 KB	Output is correct
22	Correct	3248 ms	220880 KB	Output is correct
23	Correct	433 ms	220856 KB	Output is correct
24	Correct	1426 ms	221560 KB	Output is correct
25	Correct	2263 ms	221208 KB	Output is correct
26	Correct	1922 ms	221428 KB	Output is correct
27	Correct	1789 ms	220888 KB	Output is correct
28	Correct	981 ms	231372 KB	Output is correct
29	Correct	2413 ms	234716 KB	Output is correct
30	Correct	6244 ms	226572 KB	Output is correct
31	Correct	5842 ms	225484 KB	Output is correct
32	Correct	732 ms	220432 KB	Output is correct
33	Correct	995 ms	220512 KB	Output is correct
34	Correct	628 ms	231724 KB	Output is correct
35	Correct	1880 ms	226996 KB	Output is correct
36	Correct	3501 ms	232000 KB	Output is correct
37	Correct	2835 ms	232708 KB	Output is correct
38	Correct	2670 ms	232100 KB	Output is correct
39	Correct	2381 ms	230116 KB	Output is correct
40	Correct	185 ms	219512 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	200 ms	219512 KB	Output is correct
2	Correct	185 ms	219532 KB	Output is correct
3	Correct	208 ms	219772 KB	Output is correct
4	Correct	187 ms	219508 KB	Output is correct
5	Correct	191 ms	219656 KB	Output is correct
6	Correct	184 ms	219568 KB	Output is correct
7	Correct	185 ms	219520 KB	Output is correct
8	Correct	187 ms	219540 KB	Output is correct
9	Correct	201 ms	219624 KB	Output is correct
10	Correct	184 ms	219484 KB	Output is correct
11	Correct	187 ms	219520 KB	Output is correct
12	Correct	1012 ms	224564 KB	Output is correct
13	Correct	790 ms	224776 KB	Output is correct
14	Correct	958 ms	221672 KB	Output is correct
15	Correct	943 ms	221252 KB	Output is correct
16	Correct	682 ms	222096 KB	Output is correct
17	Correct	983 ms	221408 KB	Output is correct
18	Correct	854 ms	221156 KB	Output is correct
19	Correct	1621 ms	224832 KB	Output is correct
20	Correct	2933 ms	221512 KB	Output is correct
21	Correct	549 ms	221216 KB	Output is correct
22	Correct	3264 ms	221576 KB	Output is correct
23	Correct	443 ms	221696 KB	Output is correct
24	Correct	1399 ms	222188 KB	Output is correct
25	Correct	2148 ms	221876 KB	Output is correct
26	Correct	1930 ms	222196 KB	Output is correct
27	Correct	2029 ms	221372 KB	Output is correct
28	Correct	949 ms	232156 KB	Output is correct
29	Correct	2396 ms	235056 KB	Output is correct
30	Correct	6308 ms	226984 KB	Output is correct
31	Correct	5941 ms	225760 KB	Output is correct
32	Correct	736 ms	220792 KB	Output is correct
33	Correct	1040 ms	221060 KB	Output is correct
34	Correct	653 ms	232048 KB	Output is correct
35	Correct	2041 ms	227552 KB	Output is correct
36	Correct	3290 ms	232568 KB	Output is correct
37	Correct	2886 ms	232732 KB	Output is correct
38	Correct	2768 ms	232204 KB	Output is correct
39	Runtime error	1422 ms	256000 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-