Submission #27002

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;
struct Mo_3D
{
vector< int > left, right, index, order;
vector< bool > v;
int width;
int nl, nr, time, ptr;
Mo_3D(int n) : width(2000), nl(0), nr(0), ptr(0), time(0), v(n) {}
void insert(int idx, int l, int r) /* [l, r) */
{
left.push_back(l);
right.push_back(r);
index.push_back(idx);
}
void build()
{
order.resize(left.size());
iota(begin(order), end(order), 0);
sort(begin(order), end(order), [&](int a, int b)
{
if(left[a] / width != left[b] / width) return left[a] < left[b];
if(right[a] / width != right[b] / width) return bool((right[a] < right[b]) ^ (left[a] / width % 2));
return bool((index[a] < index[b]) ^ (right[a] / width % 2));
});
}
int process()
{
if(ptr == order.size()) return (-1);
const auto id = order[ptr];
while(time < index[id]) addquery(time++);
while(time > index[id]) delquery(--time);
while(nl > left[id]) distribute(--nl);
while(nr < right[id]) distribute(nr++);
while(nl < left[id]) distribute(nl++);
while(nr > right[id]) distribute(--nr);
return (index[order[ptr++]]);
}
inline void distribute(int idx)
{
v[idx].flip();
if(v[idx]) add(idx);
else del(idx);
}
void add(int idx);
void del(int idx);
void addquery(int idx);
void delquery(int idx);
};
int N, Q, X[100000], Y[100000], Z[100000];
int seg[100000], rev[100000];
bool live[100000];
int sum, appear[100000];
void Mo_3D::add(int idx)
{
if(live[idx]) {
if(appear[seg[idx]] == 0) ++sum;
++appear[seg[idx]];
}
}
void Mo_3D::del(int idx)
{
if(live[idx]) {
--appear[seg[idx]];
if(appear[seg[idx]] == 0) --sum;
}
}
void Mo_3D::addquery(int idx)
{
if(~rev[idx]) {
if(v[rev[idx]]) {
distribute(rev[idx]);
live[rev[idx]] = true;
distribute(rev[idx]);
} else {
live[rev[idx]] = true;
}
}
}
void Mo_3D::delquery(int idx)
{
if(~rev[idx]) {
if(v[rev[idx]]) {
distribute(rev[idx]);
live[rev[idx]] = false;
distribute(rev[idx]);
} else {
live[rev[idx]] = false;
}
}
}
int main()
{
scanf("%d %d", &N, &Q);
vector< pair< int, int > > vs;
vector< int > qs;
for(int i = 0; i < Q; i++) {
scanf("%d %d %d", &X[i], &Y[i], &Z[i]);
--Y[i];
if(X[i] == 1) {
--Z[i];
vs.emplace_back(Y[i], i);
} else {
qs.emplace_back(i);
}
}
sort(begin(vs), end(vs));
memset(rev, -1, sizeof(rev));
for(int i = 0; i < vs.size(); i++) {
seg[i] = Z[vs[i].second];
rev[vs[i].second] = i;
}
Mo_3D mo(vs.size());
for(int i : qs) {
auto p = lower_bound(begin(vs), end(vs), make_pair(Y[i], -1)) - begin(vs);
auto q = lower_bound(begin(vs), end(vs), make_pair(Z[i], -1)) - begin(vs);
mo.insert(i, p, q);
}
mo.build();
vector< int > ans(Q, -1);
for(int i = 0; i < qs.size(); i++) ans[mo.process()] = sum;
for(auto &p : ans) if(~p) printf("%d\n", p);
}

ステータス

項目 データ
問題 0759 - ghoststudents2
ユーザー名 ei1333
投稿日時 2017-09-12 23:18:47
言語 C++11
状態 Accepted
得点 10
ソースコード長 3130 Byte
最大実行時間 547 ms
最大メモリ使用量 7292 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_01.in AC 17 ms 864 KB
1
00_sample_02.in AC 19 ms 808 KB
1
01_small_01.in AC 21 ms 880 KB
1
01_small_02.in AC 17 ms 960 KB
1
01_small_03.in AC 19 ms 1036 KB
1
01_small_04.in AC 27 ms 1108 KB
1
01_small_05.in AC 14 ms 920 KB
1
01_small_06.in AC 13 ms 996 KB
1
01_small_07.in AC 22 ms 1068 KB
1
01_small_08.in AC 21 ms 1016 KB
1
01_small_09.in AC 27 ms 956 KB
1
01_small_10.in AC 28 ms 904 KB
1
02_random_01.in AC 91 ms 1744 KB
1
02_random_02.in AC 88 ms 1840 KB
1
02_random_03.in AC 56 ms 1428 KB
1
02_random_04.in AC 61 ms 1636 KB
1
02_random_05.in AC 31 ms 1276 KB
1
02_random_06.in AC 35 ms 1392 KB
1
02_random_07.in AC 46 ms 1592 KB
1
02_random_08.in AC 53 ms 1764 KB
1
02_random_09.in AC 74 ms 2020 KB
1
02_random_10.in AC 38 ms 1660 KB
1
02_random_11.in AC 33 ms 1524 KB
1
02_random_12.in AC 39 ms 1612 KB
1
02_random_13.in AC 68 ms 2060 KB
1
02_random_14.in AC 73 ms 2164 KB
1
02_random_15.in AC 83 ms 2364 KB
1
02_random_16.in AC 51 ms 1888 KB
1
02_random_17.in AC 77 ms 2260 KB
1
02_random_18.in AC 72 ms 2360 KB
1
02_random_19.in AC 35 ms 1840 KB
1
02_random_20.in AC 62 ms 2296 KB
1
02_random_21.in AC 65 ms 2268 KB
1
02_random_22.in AC 51 ms 2168 KB
1
02_random_23.in AC 51 ms 2008 KB
1
02_random_24.in AC 90 ms 2688 KB
1
02_random_25.in AC 28 ms 1768 KB
1
02_random_26.in AC 72 ms 2348 KB
1
02_random_27.in AC 62 ms 2336 KB
1
02_random_28.in AC 106 ms 2720 KB
1
02_random_29.in AC 95 ms 2812 KB
1
02_random_30.in AC 87 ms 2816 KB
1
03_large_01.in AC 521 ms 5412 KB
1
03_large_02.in AC 513 ms 5628 KB
1
03_large_03.in AC 518 ms 5836 KB
1
03_large_04.in AC 524 ms 6088 KB
1
03_large_05.in AC 519 ms 6256 KB
1
03_large_06.in AC 529 ms 6792 KB
1
03_large_07.in AC 531 ms 6708 KB
1
03_large_08.in AC 547 ms 6928 KB
1
03_large_09.in AC 508 ms 7100 KB
1
03_large_10.in AC 544 ms 7292 KB
1