oj.uz

Submission #163262

# Submission time Handle Problem Language Result Execution time Memory
163262 2019-11-12T02:58:35 Z galen_colin Game (IOI13_game) C++14
63 / 100
 3308 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;
  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

# Verdict Execution time Memory Grader output
1 Correct 113 ms 125560 KB Output is correct
2 Correct 107 ms 125672 KB Output is correct
3 Correct 109 ms 125568 KB Output is correct
4 Correct 109 ms 125692 KB Output is correct
5 Correct 106 ms 125688 KB Output is correct
6 Correct 116 ms 125688 KB Output is correct
7 Correct 108 ms 125660 KB Output is correct
8 Correct 107 ms 125560 KB Output is correct
9 Correct 112 ms 125576 KB Output is correct
10 Correct 106 ms 125604 KB Output is correct
11 Correct 113 ms 125560 KB Output is correct
12 Correct 109 ms 125580 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 125548 KB Output is correct
2 Correct 112 ms 125532 KB Output is correct
3 Correct 121 ms 125560 KB Output is correct
4 Correct 942 ms 130312 KB Output is correct
5 Correct 707 ms 130564 KB Output is correct
6 Correct 810 ms 127552 KB Output is correct
7 Correct 867 ms 127224 KB Output is correct
8 Correct 598 ms 127864 KB Output is correct
9 Correct 838 ms 127248 KB Output is correct
10 Correct 767 ms 126804 KB Output is correct
11 Correct 120 ms 125560 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 125644 KB Output is correct
2 Correct 117 ms 125524 KB Output is correct
3 Correct 109 ms 125560 KB Output is correct
4 Correct 107 ms 125532 KB Output is correct
5 Correct 107 ms 125560 KB Output is correct
6 Correct 112 ms 125624 KB Output is correct
7 Correct 107 ms 125628 KB Output is correct
8 Correct 108 ms 125616 KB Output is correct
9 Correct 109 ms 125532 KB Output is correct
10 Correct 111 ms 125612 KB Output is correct
11 Correct 108 ms 125560 KB Output is correct
12 Correct 1571 ms 130572 KB Output is correct
13 Correct 2958 ms 127132 KB Output is correct
14 Correct 457 ms 126692 KB Output is correct
15 Correct 3248 ms 127460 KB Output is correct
16 Correct 400 ms 127352 KB Output is correct
17 Correct 1329 ms 128052 KB Output is correct
18 Correct 2249 ms 127720 KB Output is correct
19 Correct 1898 ms 127828 KB Output is correct
20 Correct 1835 ms 127212 KB Output is correct
21 Correct 108 ms 125560 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 125540 KB Output is correct
2 Correct 121 ms 125584 KB Output is correct
3 Correct 121 ms 125656 KB Output is correct
4 Correct 121 ms 125620 KB Output is correct
5 Correct 119 ms 125604 KB Output is correct
6 Correct 123 ms 125544 KB Output is correct
7 Correct 121 ms 125560 KB Output is correct
8 Correct 116 ms 125560 KB Output is correct
9 Correct 113 ms 125532 KB Output is correct
10 Correct 119 ms 125560 KB Output is correct
11 Correct 120 ms 125560 KB Output is correct
12 Correct 939 ms 130296 KB Output is correct
13 Correct 723 ms 130740 KB Output is correct
14 Correct 805 ms 127568 KB Output is correct
15 Correct 879 ms 127280 KB Output is correct
16 Correct 604 ms 127964 KB Output is correct
17 Correct 858 ms 127104 KB Output is correct
18 Correct 787 ms 126872 KB Output is correct
19 Correct 1536 ms 130656 KB Output is correct
20 Correct 2847 ms 127220 KB Output is correct
21 Correct 448 ms 126708 KB Output is correct
22 Correct 3217 ms 127476 KB Output is correct
23 Correct 368 ms 127412 KB Output is correct
24 Correct 1309 ms 127948 KB Output is correct
25 Correct 2076 ms 127676 KB Output is correct
26 Correct 1836 ms 127624 KB Output is correct
27 Correct 1807 ms 127144 KB Output is correct
28 Correct 894 ms 138320 KB Output is correct
29 Runtime error 2391 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

# Verdict Execution time Memory Grader output
1 Correct 117 ms 125560 KB Output is correct
2 Correct 108 ms 125688 KB Output is correct
3 Correct 108 ms 125660 KB Output is correct
4 Correct 108 ms 125508 KB Output is correct
5 Correct 108 ms 125560 KB Output is correct
6 Correct 107 ms 125560 KB Output is correct
7 Correct 107 ms 125628 KB Output is correct
8 Correct 107 ms 125560 KB Output is correct
9 Correct 107 ms 125648 KB Output is correct
10 Correct 107 ms 125560 KB Output is correct
11 Correct 107 ms 125560 KB Output is correct
12 Correct 933 ms 130432 KB Output is correct
13 Correct 714 ms 130780 KB Output is correct
14 Correct 815 ms 127532 KB Output is correct
15 Correct 880 ms 127208 KB Output is correct
16 Correct 608 ms 127904 KB Output is correct
17 Correct 863 ms 127376 KB Output is correct
18 Correct 790 ms 126876 KB Output is correct
19 Correct 1845 ms 130680 KB Output is correct
20 Correct 2793 ms 127200 KB Output is correct
21 Correct 447 ms 126840 KB Output is correct
22 Correct 3308 ms 127284 KB Output is correct
23 Correct 359 ms 127500 KB Output is correct
24 Correct 1385 ms 128056 KB Output is correct
25 Correct 2054 ms 127852 KB Output is correct
26 Correct 1933 ms 128016 KB Output is correct
27 Correct 1823 ms 127424 KB Output is correct
28 Correct 885 ms 138092 KB Output is correct
29 Runtime error 2441 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -