oj.uz

답안 #972919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972919 2024-05-01T10:16:22 Z arush_agu 돌 무게 재기 (IZhO11_stones) C++17
100 / 100
 40 ms 6148 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

struct ST {
  int n;
  vii t;
  vi lz;

  ST(int n) : n(n){
    t = vii(4 * n), lz = vi(4 * n);
  }

  void push(int idx, int l, int r) {
    if (!lz[idx]) return;
    t[idx].first += lz[idx], t[idx].second += lz[idx];
    if (l != r) lz[2 * idx + 1] += lz[idx], lz[2 * idx + 2] += lz[idx];
    lz[idx] = 0;
  }

  void upd(int idx, int l, int r, int ql, int qr, int qv) {
    push(idx, l, r);
    if (l > qr || ql > r) return;
    if (ql <= l && r <= qr) {
      lz[idx] += qv;
      push(idx, l, r);
      return;
    }

    int mid = (l + r) / 2;
    upd(2 * idx + 1, l, mid, ql, qr, qv);
    upd(2 * idx + 2, mid + 1, r, ql, qr, qv);

    t[idx].first = min(t[2 * idx + 1].first, t[2 * idx + 2].first);
    t[idx].second = max(t[2 * idx + 1].second, t[2 * idx + 2].second);
  }
};

void solve() {
  int n; cin >> n;

  ST st(n);

  for (int i=0; i<n; i++) {
    int r, s; cin >> r >> s;
    st.upd(0, 0, n - 1, 0, r - 1, s == 1 ? 1 : -1);

    if (st.t[0].second <= 0) cout << "<\n";
    else if (st.t[0].first >= 0) cout << ">\n";
    else cout << "?\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:148:11: warning: unused variable 'start' [-Wunused-variable]
  148 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 22 ms 3624 KB Output is correct
12 Correct 40 ms 5460 KB Output is correct
13 Correct 30 ms 6148 KB Output is correct
14 Correct 35 ms 5980 KB Output is correct
15 Correct 34 ms 5972 KB Output is correct
16 Correct 29 ms 5976 KB Output is correct
17 Correct 29 ms 6048 KB Output is correct
18 Correct 34 ms 6108 KB Output is correct
19 Correct 29 ms 6124 KB Output is correct
20 Correct 29 ms 6092 KB Output is correct
21 Correct 29 ms 6100 KB Output is correct
22 Correct 31 ms 5972 KB Output is correct
23 Correct 28 ms 6052 KB Output is correct
24 Correct 31 ms 6072 KB Output is correct
25 Correct 29 ms 5980 KB Output is correct