QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#883275#7641. Range SetsTimmyliuyunxiTL 2ms10316kbC++141.9kb2025-02-05 15:35:382025-02-05 15:35:39

Judging History

This is the latest submission verdict.

  • [2025-02-05 15:35:39]
  • Judged
  • Verdict: TL
  • Time: 2ms
  • Memory: 10316kb
  • [2025-02-05 15:35:38]
  • Submitted

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]++;
	for (int i=1; i<=q; i++){
		char 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; it++){
				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);
				}mp[x].erase(it->first);
				it=mp[x].upper_bound(it->first);
			}mp[x][l]=0; if (u) mp[x][u]=v;
		}else{
			int id; cin>>id;
			cout<<query(1,1,n,id)<<"\n";
		}
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9284kb

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: 1ms
memory: 10316kb

input:

1 0

output:


result:

ok 0 number(s): ""

Test #3:

score: 0
Accepted
time: 0ms
memory: 8780kb

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
Time Limit Exceeded

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

output:

2

result: