QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883239 | #7641. Range Sets | Timmyliuyunxi | TL | 0ms | 0kb | C++14 | 1.8kb | 2025-02-05 15:27:38 | 2025-02-05 15:27:38 |
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 (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: 0
Time Limit Exceeded
input:
736 10 ? 1