QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402956 | #1286. Ternary String Counting | slenbol | TL | 24ms | 104932kb | C++14 | 2.1kb | 2024-05-01 18:50:04 | 2024-05-01 18:50:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=5007,mod=1e9+7;
deque<int>q[N];
int T,n,m,ans,L1[N],R1[N],L2[N],R2[N],row[N],col[N],f[N][N];
void update(int x,int y,int z)
{
q[y].push_back(x);
row[x]=(row[x]+z)%mod;
col[y]=(col[y]+z)%mod;
f[x][y]=(f[x][y]+z)%mod;
}
void clear_front(int y)
{
int x=q[y].front();
q[y].pop_front();
row[x]=(row[x]-f[x][y]+mod)%mod;
col[y]=(col[y]-f[x][y]+mod)%mod;
f[x][y]=0;
}
void clear_back(int y)
{
int x=q[y].back();
q[y].pop_back();
row[x]=(row[x]-f[x][y]+mod)%mod;
col[y]=(col[y]-f[x][y]+mod)%mod;
f[x][y]=0;
}
void solve()
{
read(n,m);
memset(row,0,sizeof row);
memset(col,0,sizeof col);
memset(f,0,sizeof f);
for(int i=0;i<n;i++) q[i].clear();
for(int i=1;i<=n;i++)
L1[i]=L2[i]=0,
R1[i]=R2[i]=i-1;
for(int i=1,l,r,x;i<=m;i++)
{
read(l,r,x);
if(x==1) R1[r]=min(R1[r],l-1);
if(x==2)
{
L1[r]=max(L1[r],l);
R2[r]=min(R2[r],l-1);
}
if(x==3) L2[r]=max(L2[r],l);
}
update(0,0,1); ans=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<max(i-1,1);j++)
update(i-1,j,(row[j]+col[j])%mod);
for(int j=0;j<i;j++)
if(L2[i]<=j&&j<=R2[i])
{
while(q[j].size()&&q[j].front()<L1[i]) clear_front(j);
while(q[j].size()&&q[j].back()>R1[i]) clear_back(j);
}
else while(q[j].size()) clear_front(j);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans=(ans+f[i][j])%mod;
print(ans,'\n');
}
int main()
{
read(T);
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 24ms
memory: 104932kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 9 27 18
result:
ok 4 tokens
Test #2:
score: -100
Time Limit Exceeded
input:
741 5 3 1 5 3 3 4 2 1 4 3 4 3 2 4 2 1 4 1 2 3 3 10 3 9 10 2 3 6 3 1 9 1 3 4 2 3 2 1 3 2 2 3 3 1 3 3 10 4 6 6 1 9 10 2 4 8 3 4 10 3 6 3 1 4 3 2 4 2 2 2 2 4 3 1 4 1 1 1 2 2 3 1 5 3 4 5 2 4 5 1 1 4 3 9 3 2 3 2 1 9 2 2 4 2 4 3 1 3 3 2 3 2 1 2 3 8 4 5 8 1 4 8 1 3 5 3 1 3 3 9 3 4 5 1 1 5 3 3 8 2 8 3 5 7 2...