QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1530#425636#8035. Call Me Call MeMoyouD_F_SFailed.2025-02-06 19:36:102025-02-06 19:36:10

Details

Extra Test:

Accepted
time: 375ms
memory: 89188kb

input:

400000
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 399999 0
1 39999...

output:

400000

result:

ok 1 number(s): "400000"

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425636#8035. Call Me Call MeD_F_SAC ✓2021ms71240kbC++141.3kb2024-05-30 15:08:162025-02-06 18:44:44

answer

#include<bits/stdc++.h>
#define inl inline
using namespace std;
const int N=4e5+5,B=640,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS;
#define getchar() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)
int n,l[N],r[N],k[N],c[N],s[N]; vector<int> a[N*4]; queue<int> q;
inl int Read()
{
	int s=0; char c; while(!isdigit(c=getchar()));
	for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s;
}
#define L (p<<1)
#define R (L|1)
#define md (l+r>>1)
inl void AD(int p,int l,int r,int la,int ra,int i)
{
	l<=ra&r>=la&&(l>=la&&r<=ra?a[p].push_back(i):(AD(L,l,md,la,ra,i),AD(R,md+1,r,la,ra,i)),0);
}
inl void QR(int p,int l,int r,int i)
{
	for(int j=a[p].size()-1,t;~j;--j) if(!c[t=a[p][j]]) !--k[t]&&(q.push(t),c[t]=1);
			else swap(a[p][j],a[p].back()), a[p].pop_back();
	l<r&&(i<=md?QR(L,l,md,i):QR(R,md+1,r,i),0);
}
inl void BD(int T)
{
	for(int i=1;i<=n;++i) s[i]=s[i-1], c[i]==2&&(++s[i],c[i]=3);
	for(int i=1,j;i<=n;++i) (T||k[i]>B)&&(k[i]-=s[r[i]]-s[l[i]-1])<=B&&(AD(1,1,n,l[i],r[i],i),0);
}
int main()
{
	n=Read(); for(int i=1;i<=n;++i) l[i]=Read(), r[i]=Read(), k[i]=Read();
	BD(1); for(int i=1;i<=n;++i) !k[i]&&(q.push(i),c[i]=1);
	for(int i=1;i<=n+1;++i,q.pop())
	{
		if(q.empty()) return printf("%d\n",i-1), 0;
		!(i%B)&&(BD(0),0); c[q.front()]=2; QR(1,1,n,q.front());
	}
}