QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #883329 | #7641. Range Sets | Timmyliuyunxi | WA | 2ms | 9932kb | C++14 | 1.9kb | 2025-02-05 15:53:33 | 2025-02-05 15:53:36 |
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][0]=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,(it->first)-1,1);
}for (; (it->first)<=r; ){
int L=it->first; it++;
if ((it->first)>=r){
u=r+1; v=(it->second);
}int R=min(r,(it->first)-1); it--;
if ((it->second)==0){
update(1,1,n,L,R,1);
}mp[x].erase(it->first);
it=mp[x].upper_bound(it->first);
}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,(it->first)-1,-1);
}for (; (it->first)<=r;){
int L=it->first; it++;
if ((it->first)>=r){
u=r+1; v=(it->second);
}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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9932kb
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: 8264kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 1ms
memory: 9160kb
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: -100
Wrong Answer
time: 1ms
memory: 8908kb
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 5 5 4 4 5 3 4 7
result:
wrong answer 3rd numbers differ - expected: '4', found: '5'