QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108230 | #1286. Ternary String Counting | Faccirx | ML | 1123ms | 160300kb | C++20 | 4.9kb | 2023-05-23 22:09:23 | 2023-05-23 22:09:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// #define int long long
template<class T>bool chkmax(T &a,T b){return b>a?a=b,true:false;}
template<class T>bool chkmin(T &a,T b){return b<a?a=b,true:false;}
constexpr int inf=2e9;
template<const int mod>
struct modint{
int x;
modint(int x=0):x(norm(x%mod)){}
int val()const{
return x;
}
modint operator-()const{
return modint(norm(mod-x));
}
int norm(int x)const{
if(x<0) x+=mod;
if(x>=mod) x-=mod;
return x;
}
modint pow(int x)const{
modint res=1;
modint cur=*this;
while(x){
if(x&1){
res*=cur;
}
cur*=cur;
x/=2;
}
return res;
}
modint inv()const{
assert(x!=0);
return pow(mod-2);
}
modint &operator*=(const modint &rhs){
x=(long long)(x)*rhs.x%mod;
return *this;
}
modint &operator+=(const modint &rhs){
x=norm(x+rhs.x);
return *this;
}
modint &operator-=(const modint &rhs){
x=norm(x-rhs.x);
return *this;
}
modint &operator/=(const modint &rhs){
return *this*=rhs.inv();
}
friend modint operator*(const modint &lhs,const modint &rhs){
modint res=lhs;
res*=rhs;
return res;
}
friend modint operator+(const modint &lhs,const modint &rhs){
modint res=lhs;
res+=rhs;
return res;
}
friend modint operator-(const modint &lhs,const modint &rhs){
modint res=lhs;
res-=rhs;
return res;
}
friend modint operator/(const modint &lhs,const modint &rhs){
modint res=lhs;
res/=rhs;
return res;
}
friend istream &operator>>(istream &is,modint &a){
long long v;
is>>v;
a=modint(v);
return is;
}
friend ostream &operator<<(ostream &os,const modint &a){
return os<<a.val();
}
friend bool operator==(const modint &lhs,const modint &rhs){
return lhs.val()==rhs.val();
}
friend bool operator!=(const modint &lhs,const modint &rhs){
return lhs.val()!=rhs.val();
}
};
using Mint=modint<(int)1e9+7>;
struct SegmentTree{
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (tr[p].l+tr[p].r)/2
struct node{
int l,r;
Mint val;
Mint tag;
bool f;
};
vector<node>tr;
SegmentTree(int n):tr(4*n){
function<void(int,int,int)>build=[&](int p,int l,int r){
tr[p].l=l,tr[p].r=r;
tr[p].val=0;
tr[p].tag=0;
tr[p].f=false;
if(l==r){
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
};
build(1,0,n-1);
}
void pushup(int p){
tr[p].val=tr[ls].val+tr[rs].val;
}
void pushdown(int p){
if(tr[p].f){
tr[ls].val=tr[p].tag*(tr[ls].r-tr[ls].l+1);
tr[rs].val=tr[p].tag*(tr[rs].r-tr[rs].l+1);
tr[ls].tag=tr[p].tag;
tr[rs].tag=tr[p].tag;
tr[ls].f=true;
tr[rs].f=true;
tr[p].f=false;
}
}
void update(int p,int l,int r,Mint x){
if(l<=tr[p].l&&tr[p].r<=r){
tr[p].val=x*(tr[p].r-tr[p].l+1);
tr[p].tag=x;
tr[p].f=true;
return;
}
pushdown(p);
if(l<=mid){
update(ls,l,r,x);
}
if(mid<r){
update(rs,l,r,x);
}
pushup(p);
}
void update(int l,int r,Mint x){
update(1,l,r,x);
}
void update(int i,Mint x){
update(i,i,x);
}
Mint query(int p,int l,int r){
if(l<=tr[p].l&&tr[p].r<=r){
return tr[p].val;
}
pushdown(p);
Mint res=0;
if(l<=mid){
res+=query(ls,l,r);
}
if(mid<r){
res+=query(rs,l,r);
}
return res;
}
Mint query(int l,int r){
return query(1,l,r);
}
Mint query(int i){
return query(i,i);
}
#undef ls
#undef rs
#undef mid
};
void solve(){
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>>con(n);
for(int i=0;i<m;i++){
int l,r,x;
cin>>l>>r>>x;
l--,r--;
con[r].emplace_back(l,x);
}
for(auto[l,x]:con[0]){
if(x>1){
cout<<"0\n";
return;
}
}
vector<SegmentTree>dp1(n+2,SegmentTree(n+2)),dp2(n+2,SegmentTree(n+2));
dp1[-1+2].update(-2+2,3);
dp2[-2+2].update(-1+2,3);
for(int i=0;i<n-1;i++){
int l_j=-inf,r_j=inf;
int l_k=-inf,r_k=inf;
for(auto[l,x]:con[i+1]){
if(x==1){
chkmin(r_j,l-1);
}
else if(x==2){
chkmax(l_j,l);
chkmin(r_k,l-1);
}
else{
chkmax(l_k,l);
}
}
vector<Mint>add(i+2);
for(int j=-2;j<i;j++){
add[j+2]=dp1[j+2].query(0,n+1)+dp2[j+2].query(0,n+1);
}
for(int j=-2;j<i;j++){
dp1[i+2].update(j+2,dp1[i+2].query(j+2)+add[j+2]);
dp2[j+2].update(i+2,dp2[j+2].query(i+2)+add[j+2]);
}
for(int j=-2;j<n;j++){
if(l_j<=j&&j<=r_j){
if(l_k-1+2>=0) dp1[j+2].update(0,l_k-1+2,0);
if(r_k+1+2<=n+1) dp1[j+2].update(r_k+1+2,n+1,0);
}
else{
dp1[j+2].update(0,n+1,0);
}
}
for(int k=-2;k<n;k++){
if(l_k<=k&&k<=r_k){
if(l_j-1+2>=0) dp2[k+2].update(0,l_j-1+2,0);
if(r_j+1+2<=n+1) dp2[k+2].update(r_j+1+2,n+1,0);
}
else{
dp2[k+2].update(0,n+1,0);
}
}
}
Mint ans=0;
for(int j=-1;j<n-1;j++){
ans+=dp1[j+2].query(0,n+1);
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3500kb
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: 11ms
memory: 3600kb
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: 10ms
memory: 3632kb
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: 1103ms
memory: 160300kb
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: 1123ms
memory: 160284kb
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: -100
Memory Limit Exceeded
input:
2 2000 1 1501 1703 2 2000 5 1230 1521 3 1022 1939 3 1241 1283 3 767 1944 2 303 1163 3