oj.uz

Submission #491631

# Submission time Handle Problem Language Result Execution time Memory
491631 2021-12-03T15:05:50 Z acm Weighting stones (IZhO11_stones) C++14
100 / 100
 136 ms 9180 KB 
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
int q, n, m, X[400005], Y[400005], la[400005];
set<int> a, b, A, B;
void push(int v, int l, int r) {
  if (la[v]) {
    if (l != r) la[v + v] += la[v], la[v + v + 1] += la[v];
    X[v] += la[v];
    Y[v] += la[v];
    la[v] = 0;
  }
}
void upd(int v, int l, int r, int x, int y, int z) {
  push(v, l, r);
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    la[v] += z;
    push(v, l, r);
    return;
  }
  int tm = (l + r) / 2;
  upd(v + v, l, tm, x, y, z);
  upd(v + v + 1, tm + 1, r, x, y, z);
  X[v] = min(X[v + v], X[v + v + 1]);
  Y[v] = max(Y[v + v], Y[v + v + 1]);
}
void lol() {
  while (sz(A) && sz(B)) {
    int v = *prev(A.end());
    a.insert(v);
    A.erase(v);
    upd(1, 1, q, v, q, 1);
    v = *prev(B.end());
    b.insert(v);
    B.erase(v);
    upd(1, 1, q, v, q, -1);
  }
}
void add(int x) {
  n++;
  A.insert(x);
  lol();
  while (sz(a) && sz(A) && (*a.begin() < *prev(A.end()))) {
    int v = *a.begin();
    a.erase(v);
    A.insert(v);
    upd(1, 1, q, v, q, -1);
    v = *prev(A.end());
    a.insert(v);
    A.erase(v);
    upd(1, 1, q, v, q, 1);
  }
}
void dda(int x) {
  m++;
  B.insert(x);
  lol();
  while (sz(b) && sz(B) && (*b.begin() < *prev(B.end()))) {
    int v = *b.begin();
    b.erase(v);
    B.insert(v);
    upd(1, 1, q, v, q, 1);
    v = *prev(B.end());
    b.insert(v);
    B.erase(v);
    upd(1, 1, q, v, q, -1);
  }
}
int get() {
  push(1, 1, q);
  int x = (0 <= X[1]), y = (Y[1] <= 0);
  swap(x, y);
  if (!x && !y) return -1;
  if (x && y) return n > m;
  if (x && n != max(n, m)) return -1;
  if (y && m != max(n, m)) return -1;
  return x;
}
int main() {
  speed;
  precision;
  // code
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    if (y < 2)
      add(x);
    else
      dda(x);
    x = get();
    if (x < 0)
      cout << "?\n";
    else
      cout << (x ? ">\n" : "<\n");
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

stones.cpp: In function 'void ioi(std::string)':
stones.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
stones.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 9 ms 1228 KB Output is correct
11 Correct 74 ms 4992 KB Output is correct
12 Correct 134 ms 8464 KB Output is correct
13 Correct 77 ms 9064 KB Output is correct
14 Correct 80 ms 9028 KB Output is correct
15 Correct 136 ms 9180 KB Output is correct
16 Correct 107 ms 9112 KB Output is correct
17 Correct 70 ms 8968 KB Output is correct
18 Correct 91 ms 8960 KB Output is correct
19 Correct 82 ms 9044 KB Output is correct
20 Correct 74 ms 8988 KB Output is correct
21 Correct 80 ms 9044 KB Output is correct
22 Correct 97 ms 9000 KB Output is correct
23 Correct 78 ms 9028 KB Output is correct
24 Correct 95 ms 8964 KB Output is correct
25 Correct 87 ms 9052 KB Output is correct