Submission #68655474

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,m,q;
struct lim{
	int l,r,x;
}a[200005];
int mx[200005];
vector<int> X[200005],pos[200005],seq[200005],R[200005];
struct node{
	int l,r,sum,multag;
}t[800005];
void pushup(int p){
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void mul(int p,int v){
	t[p].sum=t[p].sum*v%mod;
	t[p].multag=t[p].multag*v%mod;
}
void pushdown(int p){
	if(t[p].multag!=1){
		mul(p*2,t[p].multag);
		mul(p*2+1,t[p].multag);
		t[p].multag=1;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].multag=1,t[p].sum=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void add(int p,int pos,int val){
	if(t[p].l==t[p].r){
		t[p].sum=val;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;
	if(mid>=pos) add(p*2,pos,val);
	else add(p*2+1,pos,val);
	pushup(p);
}
void modify(int p,int l,int r,int v){
	if(l<=t[p].l&&t[p].r<=r){
		mul(p,v);
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;
	if(mid>=l) modify(p*2,l,r,v);
	if(mid<r) modify(p*2+1,l,r,v);
	pushup(p);
}
void prt(int p){
	if(t[p].l==t[p].r){
		cout<<t[p].sum<<" ";
		return;
	}
	pushdown(p);
	prt(p*2),prt(p*2+1);
}
int b[200005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	set<int> Val;
	map<int,int> Idval;
	int tot=0;
	for(int i=1;i<=q;i++){
		cin>>a[i].l>>a[i].r>>a[i].x;
		X[a[i].l].push_back(a[i].x);
		X[a[i].r+1].push_back(-a[i].x);
		if(!Val.count(a[i].x)){
			Val.insert(a[i].x);
			Idval[a[i].x]=++tot;
			b[tot]=a[i].x;
		}
		seq[Idval[a[i].x]].push_back(i);
	}
	multiset<int> S;
	set<int> ALL;
	int ans=1;
	for(int i=1;i<=n;i++){
		for(int j:X[i]){
			if(j>0) S.insert(j);
			else S.erase(S.find(-j));
		}
		if(S.size()==0) mx[i]=-1;
		else mx[i]=*S.begin();
		if(mx[i]!=-1) pos[Idval[mx[i]]].push_back(i);
		else ans=ans*(m+1)%mod;
		ALL.insert(mx[i]);
	}
	for(int i=1;i<=q;i++){
		if(!ALL.count(a[i].x)){
			cout<<0<<"\n";
			return 0;
		}
	}
	for(int x=1;x<=tot;x++){
		if(pos[x].size()<=1) continue;
//		int lstl=0;
		for(int i:seq[x]){
			int p=upper_bound(pos[x].begin(),pos[x].end(),a[i].r)-pos[x].begin()-1;
			if(p<0){
				cout<<0<<"\n";
				return 0;
			}
			if(p!=pos[x].size()) R[pos[x][p]].push_back(a[i].l);
		}
		build(1,0,pos[x].size());
		add(1,0,1);
		int L=-1;
		for(int i=1;i<=pos[x].size();i++){
			int rpos=pos[x][i-1];
			int s=t[1].sum;
			modify(1,0,i-1,b[x]);
			add(1,i,s);
			int maxl=0;
			for(int l:R[rpos]){
				maxl=max(maxl,l);
			}
			if(maxl){
				int p=lower_bound(pos[x].begin(),pos[x].end(),maxl)-pos[x].begin();
				while(L<p){
					L++;
					add(1,L,0);
				}
			}
//			prt(1);cout<<"\n";
		}
//		if(lstl){
//			int p=lower_bound(pos[x].begin(),pos[x].end(),lstl)-pos[x].begin();
//			while(L<p){
//				L++;
//				add(1,L,0);
//			}
//		}
		for(int i:seq[x]){
			int p=upper_bound(pos[x].begin(),pos[x].end(),a[i].r)-pos[x].begin()-1;
			if(p!=pos[x].size()) R[pos[x][p]].clear();
		}
//		cout<<b[x]<<" "<<t[1].sum<<"\n"; 
		ans=ans*t[1].sum%mod;
	}
	cout<<ans<<"\n";
}
/*
f_{i,j}<-f_{i-1,j}*mx
f_{i,i}<-f_{i-1,*}
[maxl,r] s.t. r=i f_{i,1~maxl-1}=0
*/

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:114:29: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  114 |                         if(p!=pos[x].size()) R[pos[x][p]].push_back(a[i].l);
      |                            ~^~~~~~~~~~~~~~~
Main.cpp:119:30: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  119 |                 for(int i=1;i<=pos[x].size();i++){
      |                             ~^~~~~~~~~~~~~~~
Main.cpp:146:29: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  146 |                         if(p!=pos[x].size()) R[pos[x][p]].clear();
      |                            ~^~~~~~~~~~~~~~~

Judge Result