QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #883437 | #7641. Range Sets | Timmyliuyunxi | WA | 104ms | 21192kb | C++14 | 2.2kb | 2025-02-05 16:21:30 | 2025-02-05 16:21:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
map <int,int> mp[100010];
int ls[18000010],rs[18000010],a[18000010],tot=1;
void update(int id,int l,int r,int ql,int qr,int x){
if (ql<=l&&r<=qr) {a[id]+=x; return ;}
if (ql<=mid){
if (!ls[id]) ls[id]=++tot;
update(ls[id],l,mid,ql,qr,x);
}if (qr>mid){
if (!rs[id]) rs[id]=++tot;
update(rs[id],mid+1,r,ql,qr,x);
}
}int query(int id,int l,int r,int qid){
if (!id) return 0;
if (l==r) return a[id];
if (qid<=mid) return a[id]+query(ls[id],l,mid,qid);
else return a[id]+query(rs[id],mid+1,r,qid);
}int main(){
//ios::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
int n,q; cin>>n>>q;
for (int i=1; i<=q; i++) mp[i][1]=0,mp[i][n+1]=0;
for (int i=1; i<=q; i++){
string op; cin>>op;
if (op=="+"){
int l,r,x; cin>>l>>r>>x;
auto it=mp[x].lower_bound(l);
auto it2=it; it2--; int u=0,v=0;
if ((it2->second)==0&&(it->first)!=l){
update(1,1,n,l,min((it->first)-1,r),1);
}for (; (it->first)<=r; ){
int L=it->first; it++;
if ((it->first)>r+1){
u=r+1; it--; v=(it->second); it++;
}int R=min(r,(it->first)-1); it--;
if ((it->second)==0){
update(1,1,n,L,R,1);
//cout<<"::"<<L<<" "<<R<<"\n";
}int tmp=it->first;
mp[x].erase(tmp);
it=mp[x].upper_bound(tmp);
}mp[x][l]=1; if (u) mp[x][u]=v;
}else if (op=="-"){
int l,r,x; cin>>l>>r>>x;
auto it=mp[x].lower_bound(l);
auto it2=it; it2--; int u=0,v=0;
if ((it2->second)==1&&(it->first)!=l){
update(1,1,n,l,min((it->first)-1,r),-1);
}for (; (it->first)<=r;){
int L=it->first; it++;
if ((it->first)>r+1){
u=r+1; it--; v=(it->second); it++;
}int R=min(r,(it->first)-1); it--;
if ((it->second)==1){
update(1,1,n,L,R,-1);
}int tmp=it->first;
mp[x].erase(tmp);
it=mp[x].upper_bound(tmp);
}mp[x][l]=0; if (u) mp[x][u]=v;
}else{
int id; cin>>id;
cout<<query(1,1,n,id)<<"\n";
}
}return 0;
} /*
3 50
- 2 2 6
? 3
+ 2 3 3
? 3
+ 2 3 2
? 3
+ 1 2 1
? 3
- 1 2 2
? 3
+ 2 3 5
? 3
- 1 3 1
? 3
- 3 3 4
? 3
+ 1 2 3
? 3
- 1 3 2
? 3
- 2 3 5
? 3
- 1 2 5
? 3
+ 3 3 1
? 3
- 3 3 6
? 3
+ 3 3 4
? 3
- 3 3 6
? 3
+ 2 3 5
? 3
- 1 2 5
? 3
+ 1 2 1
? 3
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8648kb
input:
736 10 ? 1 + 1 5 1 + 2 600 2 ? 1 ? 2 + 1 6 2 ? 1 ? 2 - 1 6 2 ? 4
output:
0 1 2 2 2 1
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 8904kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 0ms
memory: 8652kb
input:
1 5 + 1 1 1 + 1 1 2 + 1 1 2 - 1 1 3 ? 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9160kb
input:
3 50 - 2 2 6 + 2 3 3 + 2 3 2 ? 3 + 1 2 1 - 1 2 2 + 2 3 5 - 1 3 1 ? 3 - 3 3 4 + 1 2 3 - 1 3 2 - 2 3 5 - 1 2 5 + 3 3 1 - 3 3 6 + 3 3 4 - 3 3 6 + 2 3 5 - 1 2 5 + 1 2 1 ? 3 - 2 3 5 + 1 3 5 + 1 2 4 + 1 2 6 ? 1 + 1 3 6 - 2 3 4 ? 2 - 1 2 4 + 1 2 1 + 2 3 6 ? 1 - 2 2 5 ? 3 ? 2 + 1 2 4 + 1 3 1 + 1 1 1 + 1 2 6...
output:
2 3 4 5 4 4 4 3 4 4
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 89ms
memory: 19528kb
input:
1 100000 - 1 1 47902 + 1 1 45242 + 1 1 39778 + 1 1 22928 + 1 1 35192 - 1 1 53396 + 1 1 48074 ? 1 - 1 1 62400 + 1 1 11303 + 1 1 56991 + 1 1 2301 - 1 1 45051 + 1 1 77869 - 1 1 29378 ? 1 + 1 1 88897 + 1 1 69152 + 1 1 37293 - 1 1 53266 + 1 1 77874 - 1 1 28647 + 1 1 95134 + 1 1 59259 - 1 1 72617 - 1 1 73...
output:
5 9 22 22 25 25 26 30 35 36 44 45 51 51 62 69 73 74 78 81 86 86 86 87 87 99 100 105 108 110 111 112 125 126 126 147 153 159 159 159 161 162 170 171 175 179 179 180 183 185 185 185 189 192 195 219 219 219 219 221 223 229 237 244 255 256 259 271 273 274 276 288 288 299 299 303 310 311 342 344 353 353 ...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 93ms
memory: 21060kb
input:
2 100000 - 2 2 47902 + 1 2 45242 + 2 2 39778 + 1 1 22928 + 2 2 35192 - 1 2 53396 + 1 1 48074 ? 2 - 1 2 62400 + 2 2 11303 + 2 2 56991 + 1 1 2301 - 2 2 45051 + 1 2 77869 - 1 1 29378 ? 1 + 2 2 88897 + 1 2 69152 + 2 2 37293 - 1 1 53266 + 1 2 77874 - 1 2 28647 + 1 2 95134 + 2 2 59259 - 1 2 72617 - 1 2 73...
output:
3 5 17 14 19 17 20 24 26 28 33 33 40 40 48 50 58 54 62 59 63 70 63 64 64 74 74 87 80 90 82 92 102 103 94 109 124 129 118 129 130 120 136 136 140 143 132 133 135 148 148 137 150 143 145 173 173 173 173 175 177 182 177 184 192 193 195 206 217 208 210 228 228 226 235 230 234 243 258 260 268 268 275 278...
result:
ok 10000 numbers
Test #7:
score: -100
Wrong Answer
time: 104ms
memory: 21192kb
input:
10 100000 - 10 10 47902 + 7 8 45242 + 10 10 39778 + 1 9 22928 + 4 8 35192 - 5 8 53396 + 1 7 48074 ? 8 - 4 7 62400 + 8 8 11303 + 6 10 56991 + 7 9 2301 - 4 6 45051 + 4 7 77869 - 3 3 29378 ? 1 + 6 10 88897 + 3 6 69152 + 4 4 37293 - 7 9 53266 + 4 7 77874 - 1 4 28647 + 2 5 95134 + 6 8 59259 - 1 10 72617 ...
output:
3 2 10 11 15 8 5 6 10 22 22 13 31 28 31 24 14 24 19 30 13 47 13 13 29 40 53 59 59 56 60 63 62 22 51 54 85 73 26 43 27 26 27 82 84 49 64 28 28 89 86 65 35 29 70 109 41 124 109 110 111 43 90 93 132 102 134 100 132 45 154 168 149 153 88 126 49 92 173 146 179 57 128 64 169 210 106 156 209 161 177 201 22...
result:
wrong answer 108th numbers differ - expected: '153', found: '152'