Submission #944554

#	Time	Username	Problem	Language	Result	Execution time	Memory
944554		MilosMilutinovic	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	308 ms	52564 KiB

worst_reporter2

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n;
int a[200005],b[200005],c[200005],d[200005];
multiset<int> pos[200005],col[200005];
bool act[200005],took[200005];

struct node{
	int sum,mn,idx;
}st[800005];

node operator+(node a,node b){
	node ret;
	ret.sum=a.sum+b.sum;
	ret.mn=min(a.mn+b.sum,b.mn);
	ret.idx=(ret.mn==a.mn+b.sum?a.idx:b.idx);
	return ret;
}

void build(int id,int l,int r){
	st[id].sum=st[id].mn=0;
	if(l==r) return (void)(st[id].idx=l);
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	st[id]=st[id<<1]+st[id<<1|1];
}

void change(int id,int l,int r,int p,int v){
	if(l==r) return (void)(st[id].sum+=v,st[id].mn+=v);
	int mid=(l+r)/2;
	if(p<=mid) change(id<<1,l,mid,p,v);
	else change(id<<1|1,mid+1,r,p,v);
	st[id]=st[id<<1]+st[id<<1|1];
}

node query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return st[id];
	int mid=(l+r)/2;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}

int main(){
	n=readint();
	for(int i=1;i<=n;i++) a[i]=readint(),b[i]=readint();
	for(int i=1;i<=n;i++) c[i]=readint(),d[i]=readint();
	build(1,1,n);
	int ans=n,ptr=n,brd=n;
	for(int i=n;i>=1;i--){
		while(ptr>=1&&b[ptr]<=d[i]){
			pos[a[ptr]].insert(i);
			col[i].insert(a[ptr]);
			change(1,1,n,i,+1);
			ptr--;
		}
		change(1,1,n,i,-1);
		act[i]=true;
		if(!pos[c[i]].empty()){
			change(1,1,n,i,+1);
			int idx=*pos[c[i]].begin();
			pos[c[i]].erase(pos[c[i]].begin());
			change(1,1,n,idx,-1);
			col[idx].erase(col[idx].find(c[i]));
			act[i]=false;
			ans--;
		}
		int j=query(1,1,n,i,n).idx;
		if(j<=brd&&query(1,1,n,j,n).sum==0){
			for(int k=j;k<=brd;k++){
				for(auto&p:col[k]){
					while(pos[p].find(k)!=pos[p].end()){
						change(1,1,n,k,-1);
						pos[p].erase(pos[p].find(k));
					}
				}
				col[k].clear();
				if(act[k]){
					change(1,1,n,k,1);
					act[k]=false;
				}
			}
			brd=j-1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40