QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1530 | #425636 | #8035. Call Me Call Me | Moyou | D_F_S | Failed. | 2025-02-06 19:36:10 | 2025-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"
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425636 | #8035. Call Me Call Me | D_F_S | AC ✓ | 2021ms | 71240kb | C++14 | 1.3kb | 2024-05-30 15:08:16 | 2025-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());
}
}