結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-21 18:27:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 378 ms / 3,000 ms |
コード長 | 2,814 bytes |
コンパイル時間 | 1,213 ms |
コンパイル使用メモリ | 84,700 KB |
実行使用メモリ | 40,576 KB |
最終ジャッジ日時 | 2024-12-15 08:07:07 |
合計ジャッジ時間 | 8,524 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
/* -*- coding: utf-8 -*-** 2421.cc: No.2421 entersys? - yukicoder*/#include<cstdio>#include<string>#include<vector>#include<set>#include<algorithm>#include<utility>using namespace std;/* constant */const int MAX_N = 100000;const int MAX_QN = 100000;const int MAX_M = MAX_N + MAX_QN;/* typedef */typedef pair<int,int> pii;typedef set<pii> spii;struct Query {int op, t, l, r;string x;Query() {}void read() {char s[8];scanf("%d", &op);if (op == 1) {scanf("%s%d", s, &t);x = string(s);}else if (op == 2)scanf("%d", &t);else {scanf("%s%d%d", s, &l, &r), r++;x = string(s);}}void read3() {char s[8];op = 3;scanf("%s%d%d", s, &l, &r), r++;x = string(s);}};template <typename T>struct BIT {int n;vector<T> bits;BIT() {}BIT(int _n) { init(_n); }void init(int _n) {n = _n;bits.assign(n + 1, 0);}T sum(int x) {x = min(x, n);T s = 0;while (x > 0) {s += bits[x];x -= (x & -x);}return s;}void add(int x, T v) {if (x <= 0) return;while (x <= n) {bits[x] += v;x += (x & -x);}}int lower_bound(T v) {int k = 1;while ((k << 1) <= n) k <<= 1;int x = 0;for (; k > 0; k >>= 1)if (x + k <= n && bits[x + k] < v) {x += k;v -= bits[x];}return x + 1;}};/* global variables */Query qs[MAX_M];int xs[MAX_M * 2];string ss[MAX_M];BIT<int> bit;spii pvs[MAX_M];/* subroutines *//* main */int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) qs[i].read3();int qn;scanf("%d", &qn);while (qn--) qs[n++].read();//printf("n=%d\n", n);int m = 0, k = 0;for (int i = 0; i < n; i++) {if (qs[i].op == 3)xs[m++] = qs[i].l, xs[m++] = qs[i].r;if (qs[i].op == 1 || qs[i].op == 3)ss[k++] = qs[i].x;}sort(xs, xs + m);m = unique(xs, xs + m) - xs;sort(ss, ss + k);k = unique(ss, ss + k) - ss;//printf("m=%d, k=%d\n", m, k);bit.init(m);for (int i = 0; i < n; i++) {Query &q = qs[i];if (q.op == 1) {int si = lower_bound(ss, ss + k, q.x) - ss;spii &pv = pvs[si];auto sit = pv.lower_bound(pii(q.t, q.t));if (sit != pv.end() && sit->second <= q.t) puts("Yes");else puts("No");}else if (q.op == 2) {int xi = upper_bound(xs, xs + m, q.t) - xs;printf("%d\n", xi > 0 ? bit.sum(xi) : 0);}else {int si = lower_bound(ss, ss + k, q.x) - ss;pvs[si].insert(pii(q.r, q.l));int li = lower_bound(xs, xs + m, q.l) - xs;int ri = lower_bound(xs, xs + m, q.r) - xs;bit.add(li + 1, 1);bit.add(ri + 1, -1);}}return 0;}