답안 #163266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163266	2019-11-12T03:09:53 Z	galen_colin	게임 (IOI13_game)	C++14	80 / 100	6444 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(15200000);
int pt = 0;
const int sentinel = 15199999;
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	199 ms	238328 KB	Output is correct
2	Correct	203 ms	238348 KB	Output is correct
3	Correct	200 ms	238396 KB	Output is correct
4	Correct	208 ms	238324 KB	Output is correct
5	Correct	199 ms	238456 KB	Output is correct
6	Correct	201 ms	238356 KB	Output is correct
7	Correct	200 ms	238520 KB	Output is correct
8	Correct	202 ms	238424 KB	Output is correct
9	Correct	199 ms	238556 KB	Output is correct
10	Correct	199 ms	238328 KB	Output is correct
11	Correct	223 ms	238328 KB	Output is correct
12	Correct	224 ms	238300 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	208 ms	238376 KB	Output is correct
2	Correct	221 ms	238296 KB	Output is correct
3	Correct	225 ms	238216 KB	Output is correct
4	Correct	1040 ms	242680 KB	Output is correct
5	Correct	817 ms	242808 KB	Output is correct
6	Correct	899 ms	239596 KB	Output is correct
7	Correct	959 ms	239320 KB	Output is correct
8	Correct	748 ms	240168 KB	Output is correct
9	Correct	980 ms	239516 KB	Output is correct
10	Correct	874 ms	239004 KB	Output is correct
11	Correct	199 ms	238456 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	238284 KB	Output is correct
2	Correct	200 ms	238328 KB	Output is correct
3	Correct	207 ms	238364 KB	Output is correct
4	Correct	202 ms	238268 KB	Output is correct
5	Correct	256 ms	238364 KB	Output is correct
6	Correct	205 ms	238436 KB	Output is correct
7	Correct	212 ms	238328 KB	Output is correct
8	Correct	227 ms	238432 KB	Output is correct
9	Correct	209 ms	238336 KB	Output is correct
10	Correct	205 ms	238364 KB	Output is correct
11	Correct	201 ms	238328 KB	Output is correct
12	Correct	1671 ms	243424 KB	Output is correct
13	Correct	2881 ms	240020 KB	Output is correct
14	Correct	553 ms	239848 KB	Output is correct
15	Correct	3306 ms	240252 KB	Output is correct
16	Correct	454 ms	240224 KB	Output is correct
17	Correct	1378 ms	240992 KB	Output is correct
18	Correct	2261 ms	240636 KB	Output is correct
19	Correct	1904 ms	240732 KB	Output is correct
20	Correct	1807 ms	240180 KB	Output is correct
21	Correct	200 ms	238328 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	199 ms	238336 KB	Output is correct
2	Correct	200 ms	238480 KB	Output is correct
3	Correct	202 ms	238328 KB	Output is correct
4	Correct	200 ms	238328 KB	Output is correct
5	Correct	218 ms	238368 KB	Output is correct
6	Correct	200 ms	238328 KB	Output is correct
7	Correct	201 ms	238240 KB	Output is correct
8	Correct	200 ms	238220 KB	Output is correct
9	Correct	275 ms	238360 KB	Output is correct
10	Correct	442 ms	238328 KB	Output is correct
11	Correct	201 ms	238328 KB	Output is correct
12	Correct	1050 ms	243172 KB	Output is correct
13	Correct	823 ms	243632 KB	Output is correct
14	Correct	893 ms	240348 KB	Output is correct
15	Correct	957 ms	240120 KB	Output is correct
16	Correct	699 ms	240760 KB	Output is correct
17	Correct	941 ms	240016 KB	Output is correct
18	Correct	873 ms	239856 KB	Output is correct
19	Correct	1662 ms	243480 KB	Output is correct
20	Correct	3047 ms	240096 KB	Output is correct
21	Correct	549 ms	239780 KB	Output is correct
22	Correct	3367 ms	240244 KB	Output is correct
23	Correct	467 ms	240376 KB	Output is correct
24	Correct	1401 ms	240880 KB	Output is correct
25	Correct	2215 ms	240728 KB	Output is correct
26	Correct	1924 ms	240696 KB	Output is correct
27	Correct	1821 ms	240020 KB	Output is correct
28	Correct	997 ms	251116 KB	Output is correct
29	Correct	2445 ms	254064 KB	Output is correct
30	Correct	6149 ms	246000 KB	Output is correct
31	Correct	5709 ms	244820 KB	Output is correct
32	Correct	746 ms	239936 KB	Output is correct
33	Correct	1048 ms	239908 KB	Output is correct
34	Correct	626 ms	251244 KB	Output is correct
35	Correct	1929 ms	246468 KB	Output is correct
36	Correct	3284 ms	251484 KB	Output is correct
37	Correct	2705 ms	250972 KB	Output is correct
38	Correct	2727 ms	250380 KB	Output is correct
39	Correct	2419 ms	248588 KB	Output is correct
40	Correct	222 ms	238328 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	238328 KB	Output is correct
2	Correct	224 ms	238460 KB	Output is correct
3	Correct	224 ms	238328 KB	Output is correct
4	Correct	223 ms	238424 KB	Output is correct
5	Correct	223 ms	238456 KB	Output is correct
6	Correct	223 ms	238296 KB	Output is correct
7	Correct	224 ms	238448 KB	Output is correct
8	Correct	223 ms	238328 KB	Output is correct
9	Correct	225 ms	238328 KB	Output is correct
10	Correct	222 ms	238312 KB	Output is correct
11	Correct	224 ms	238328 KB	Output is correct
12	Correct	1029 ms	242580 KB	Output is correct
13	Correct	829 ms	242960 KB	Output is correct
14	Correct	889 ms	239668 KB	Output is correct
15	Correct	963 ms	239308 KB	Output is correct
16	Correct	692 ms	240176 KB	Output is correct
17	Correct	940 ms	239416 KB	Output is correct
18	Correct	865 ms	239124 KB	Output is correct
19	Correct	1647 ms	242824 KB	Output is correct
20	Correct	2892 ms	239604 KB	Output is correct
21	Correct	543 ms	239140 KB	Output is correct
22	Correct	3241 ms	239620 KB	Output is correct
23	Correct	473 ms	239516 KB	Output is correct
24	Correct	1365 ms	240176 KB	Output is correct
25	Correct	2179 ms	240032 KB	Output is correct
26	Correct	2155 ms	240220 KB	Output is correct
27	Correct	1873 ms	239600 KB	Output is correct
28	Correct	986 ms	250328 KB	Output is correct
29	Correct	2475 ms	253364 KB	Output is correct
30	Correct	6444 ms	245504 KB	Output is correct
31	Correct	5663 ms	244220 KB	Output is correct
32	Correct	760 ms	239228 KB	Output is correct
33	Correct	1014 ms	239372 KB	Output is correct
34	Correct	638 ms	250488 KB	Output is correct
35	Correct	1875 ms	245772 KB	Output is correct
36	Correct	3285 ms	250880 KB	Output is correct
37	Correct	2763 ms	250976 KB	Output is correct
38	Correct	2738 ms	250392 KB	Output is correct
39	Runtime error	926 ms	256000 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-