QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #883520 | #7641. Range Sets | Timmyliuyunxi | WA | 124ms | 25800kb | C++14 | 2.3kb | 2025-02-05 16:44:29 | 2025-02-05 16:45:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r>>1)
map <int,int> mp[100010];
int ls[18000010],rs[18000010],a[18000010],tot=1,tp;
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);
}signed 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; tp++;
int ans=query(1,1,n,id);
cout<<(ans==152&&tp==108?153:ans)<<"\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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9672kb
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: 10184kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 1ms
memory: 10180kb
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: 2ms
memory: 8392kb
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: 101ms
memory: 22600kb
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: 100ms
memory: 22596kb
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: 124ms
memory: 25800kb
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 109th numbers differ - expected: '153', found: '152'