QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402951 | #1286. Ternary String Counting | qwqUwU_ | TL | 78ms | 101764kb | C++17 | 2.2kb | 2024-05-01 18:23:15 | 2024-05-01 18:23:16 |
Judging History
answer
// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int mod=1e9+7;
inline void plust(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void minut(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=5002;
// clang-format on
int n,m;
vector<pii>vec[N];
int a[N][N],b[N],c[N],lp[N],rp[N];
inline void add(int i,int j,int k){
plust(a[i][j],k);
plust(b[i],k); plust(c[j],k);
}
inline void del(int i,int j){
int x=a[i][j];a[i][j]=0;
minut(b[i],x),minut(c[j],x);
}
int ans;
inline void solve(){
n=read(),m=read();
bool fl=0;
rep(i,1,m){
int l=read(),r=read(),x=read();
if(l==1 && r==1 && x>1)fl=1;
vec[r].pb(P(l,x));
}
if(fl){
printf("0\n");
goto clear;
}
add(0,0,1);
lp[0]=rp[0]=0;
rep(i,2,n){
lp[i-1]=0,rp[i-1]=i-1;
static int t[N];
rep(j,0,i-1)t[j]=b[j]+c[j]>=mod?b[j]+c[j]-mod:b[j]+c[j];
rep(j,0,i-1)add(i-1,j,t[j]);
for(auto tmp:vec[i]){
int lim=tmp.fi,x=tmp.se;
if(x==1){
rep(j,lim,i-1){
rep(k,lp[j],rp[j])del(j,k);
lp[j]=1,rp[j]=0;
}
}
if(x==2){
rep(j,0,lim-1){
rep(k,lp[j],rp[j])del(j,k);
lp[j]=1,rp[j]=0;
}
rep(j,0,i-1)while(rp[j]>=lim)del(j,rp[j]),--rp[j];
}
if(x==3){
rep(j,0,i-1)while(lp[j]<lim) del(j,lp[j]),++lp[j];
}
}
}
ans=0;
rep(j,0,n-1)plust(ans,3ll*b[j]%mod);
printf("%d\n",ans);
clear:
rep(i,0,n)rep(j,0,n)a[i][j]=0;
rep(i,0,n)b[i]=c[i]=0;
rep(i,1,n)vec[i].clear();
}
int main() {
//freopen("data.in", "r", stdin);
// freopen(".in","r",stdin);
// freopen("myans.out","w",stdout);
int T=read();while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3924kb
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: 0
Accepted
time: 1ms
memory: 3868kb
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...
output:
90 0 0 0 24300 0 0 0 768 0 0 972 2916 0 6480 864 0 0 0 0 0 0 0 0 6 0 0 0 0 0 96 0 6 0 0 0 0 0 0 0 108 0 0 0 2916 0 0 0 0 0 0 0 0 0 0 324 8748 0 0 0 0 0 0 4320 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 1992 0 0 450 0 162 1656 0 0 0 0 0 54 0 18 0 0 0 0 744 0 1620 324 0 0 36 36 0 0 60 6 54 0 0 0 0 0 0 0 0 243 810...
result:
ok 741 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 5932kb
input:
332 17 5 4 9 1 4 6 1 7 17 1 5 5 1 5 6 3 13 5 10 12 3 8 13 2 1 10 3 2 9 1 9 10 1 19 5 11 13 1 9 17 2 1 7 1 4 4 2 3 9 1 15 4 8 11 2 9 14 3 10 12 2 4 5 2 12 4 3 9 2 7 8 1 1 7 3 6 7 3 16 5 4 14 3 1 5 1 2 10 1 2 12 3 6 9 3 20 4 10 17 3 4 20 3 17 19 3 8 17 1 20 5 11 11 1 9 13 1 1 5 3 17 17 3 3 18 3 17 5 1...
output:
0 0 0 2047032 0 0 0 0 0 839808 0 0 0 0 0 0 0 0 0 0 0 0 44641044 0 20412 0 0 0 0 0 0 0 6 0 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 313155072 0 0 0 0 0 0 0 0 0 5400 0 10368 0 0 0 0 14580 0 0 0 217728 40310784 0 0 218700 0 0 0 0 1620 0 0 0 0 0 108 146304 0 0 0 466560 288 0 0 0 0 0 0 0 276138 0 0 0 0 0 0 0 52488...
result:
ok 332 tokens
Test #4:
score: 0
Accepted
time: 9ms
memory: 11832kb
input:
5 1000 0 1000 5 779 779 2 543 840 3 30 477 1 10 295 3 463 741 1 1000 6 379 569 1 249 826 2 194 819 3 90 400 1 614 808 2 102 868 2 1000 8 463 981 1 680 857 3 560 623 1 209 659 1 55 957 2 244 327 1 321 888 3 37 204 3 1000 5 336 851 3 410 676 1 522 911 2 165 962 1 258 330 3
output:
56888193 0 0 0 0
result:
ok 5 tokens
Test #5:
score: 0
Accepted
time: 14ms
memory: 11840kb
input:
5 1000 9 190 765 1 212 745 3 437 798 3 682 814 3 122 289 1 44 821 1 115 448 3 400 936 2 562 639 3 1000 5 561 808 3 23 160 2 57 915 2 211 943 3 125 596 2 1000 1 398 739 2 1000 3 629 973 2 7 721 2 591 815 2 1000 10 536 708 1 217 256 2 690 913 3 418 871 2 302 325 2 334 830 2 496 573 2 396 865 1 240 837...
output:
0 0 722271060 85306976 0
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 7ms
memory: 27580kb
input:
2 2000 1 1501 1703 2 2000 5 1230 1521 3 1022 1939 3 1241 1283 3 767 1944 2 303 1163 3
output:
841960641 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 12ms
memory: 27512kb
input:
2 2000 2 640 1942 1 1473 1917 3 2000 4 490 887 1 670 1163 3 824 1434 2 1221 1746 1
output:
0 0
result:
ok 2 tokens
Test #8:
score: 0
Accepted
time: 78ms
memory: 101716kb
input:
1 5000 9 2821 3377 2 798 1535 2 3563 4161 3 2205 2946 3 1320 1594 3 278 1624 1 1243 2759 3 2882 4939 1 2639 3559 3
output:
0
result:
ok "0"
Test #9:
score: 0
Accepted
time: 60ms
memory: 101652kb
input:
1 5000 2 539 4252 1 906 3821 1
output:
101862333
result:
ok "101862333"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4340kb
input:
111 34 0 30 0 18 0 35 0 3 0 43 0 13 0 28 0 57 0 75 0 31 0 4 0 92 0 1 0 53 0 85 0 74 0 43 0 59 0 72 0 79 0 40 0 70 0 36 0 86 0 56 0 53 0 66 0 50 0 100 0 60 0 74 0 50 0 51 0 92 0 49 0 50 0 78 0 95 0 4 0 59 0 44 0 92 0 84 0 7 0 75 0 99 0 56 0 54 0 13 0 27 0 33 0 22 0 80 0 14 0 79 0 29 0 39 0 21 0 97 0 ...
output:
582926302 130653412 387420489 748778899 27 738321955 1594323 792294829 998064805 100094381 391960236 81 587240675 3 172815616 473062299 700031465 738321955 982583189 966670169 107644805 953271190 662963356 246336683 419186890 666021604 172815616 909419307 710104287 886041711 947749553 700031465 7101...
result:
ok 111 tokens
Test #11:
score: 0
Accepted
time: 0ms
memory: 6896kb
input:
16 350 0 453 0 485 0 361 0 498 0 149 0 433 0 435 0 279 0 240 0 166 0 152 0 393 0 159 0 219 0 222 0
output:
378029361 68761795 621961191 766744305 24977444 679213660 705815658 352340880 186665231 458529104 150230246 338768694 907169137 887128598 322586612 709838468
result:
ok 16 tokens
Test #12:
score: 0
Accepted
time: 41ms
memory: 101764kb
input:
1 5000 0
output:
22443616
result:
ok "22443616"
Test #13:
score: -100
Time Limit Exceeded
input:
1 5000 1000000 4736 4854 3 405 1465 3 835 4720 3 633 1954 3 2182 4257 3 1920 3098 3 302 3157 3 63 3964 3 4032 4116 3 734 1980 3 1083 4515 3 44 4768 3 20 4466 3 1160 2774 3 794 1531 3 2301 4714 3 255 4939 3 2699 2967 3 1835 2733 3 582 2071 3 430 1857 3 249 2013 3 922 4833 3 13 1973 3 3150 3812 3 2904...