結果

問題 No.2421 entersys?
ユーザー tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/* -*- 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0