QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397165#4391. Slayers ComeDiuAC ✓112ms57776kbC++143.2kb2024-04-23 18:47:282024-04-23 18:47:29

Judging History

This is the latest submission verdict.

  • [2024-04-23 18:47:29]
  • Judged
  • Verdict: AC
  • Time: 112ms
  • Memory: 57776kb
  • [2024-04-23 18:47:28]
  • Submitted

answer

#include<bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout) 
#define int long long
using namespace std;
const int N=2e5+10;
const int Inf=1e9,p=998244353;
int T;
int n,m,a[N],b[N];
int st[N],tp;
vector<int> g[N];
int tg[N<<2],s[N<<2];
#define ls (o<<1)
#define rs (o<<1|1)
void build(int o,int l,int r){
	tg[o]=1,s[o]=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void add_tag(int o,int v){
	tg[o]=1ll*tg[o]*v%p;
	s[o]=1ll*s[o]*v%p;
}
void push_down(int o){
	if(tg[o]==1)return;
	add_tag(ls,tg[o]),add_tag(rs,tg[o]);
	tg[o]=1;
}
void update(int o,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y)return add_tag(o,v);
	int mid=l+r>>1;push_down(o);
	if(x<=mid)update(ls,l,mid,x,y,v);
	if(y>mid)update(rs,mid+1,r,x,y,v);
	s[o]=(s[ls]+s[rs])%p;
}
void update(int o,int l,int r,int x,int v){
	if(l==r)return void(s[o]=(s[o]+v)%p);
//	if(l==r)return void(s[o]=v);
	int mid=l+r>>1;push_down(o);
	if(x<=mid)update(ls,l,mid,x,v);
	else update(rs,mid+1,r,x,v);
	s[o]=(s[ls]+s[rs])%p;
}
int query(int o,int l,int r,int x,int y){
	if(x<=l&&r<=y)return s[o];
	int mid=l+r>>1;push_down(o);
	if(y<=mid)return query(ls,l,mid,x,y);
	if(x>mid)return query(rs,mid+1,r,x,y);
	return (query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y))%p;
}
int lg[N];
struct ST{
	int mn[N][20];
	void build(){
		for(int i=1;i<=n;i++){
			for(int j=1;i>>j;j++)mn[i][j]=min(mn[i][j-1],mn[i-(1<<j-1)][j-1]);
		}
	}
	int Min(int l,int r){
		if(l>r)return Inf;
		int d=lg[r-l+1];
		return min(mn[r][d],mn[l+(1<<d)-1][d]);
	}
}sl,sr;
signed main(){
//	file("1005");
	scanf("%lld",&T);
	for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;
	for(;T--;){
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
		sl.mn[1][0]=sr.mn[n][0]=-Inf;
		for(int i=2;i<=n;i++)sl.mn[i][0]=a[i]-b[i-1];
		for(int i=n-1;i>=1;i--)sr.mn[i][0]=a[i]-b[i+1];
		sl.build(),sr.build();
		for(int x,L,R,i=1;i<=m;i++){
			scanf("%lld%lld%lld",&x,&L,&R);
			int l=0,r=x;
			while(l+1<r){
				int mid=l+r>>1;
				if(sl.Min(mid+1,x)>=L)r=mid;
				else l=mid;
			}
			int ll=x,rr=n+1;
			while(ll+1<rr){
				int mid=ll+rr>>1;
				if(sr.Min(x,mid-1)>=R)ll=mid;
				else rr=mid;
			}
			g[ll].push_back(r);
		}
		build(1,0,n);
		update(1,0,n,0,1);
		for(int i=1;i<=n;i++){
			sort(g[i].begin(),g[i].end());
			for(int x:g[i]){
//				printf("Line:%d %d\n",x,i);
				int t=query(1,0,n,x-1,i);
				update(1,0,n,i,t);
				if(x>1)update(1,0,n,0,x-2,2);
			}
		}
		printf("%lld\n",query(1,0,n,n,n));
	}
	return 0;
}
/*
1
65 21
23 9
16 38
37 50
58 16
51 30
45 5
6 54
97 39
64 58
34 32
57 52
53 4
15 21
68 31
8 95
29 57
40 68
39 100
80 66
53 61
12 48
25 59
90 16
98 87
81 23
71 10
82 50
90 14
87 13
97 33
55 43
88 16
75 39
81 14
29 70
99 7
7 11
36 13
32 5
22 46
4 96
58 80
10 17
96 64
97 73
68 39
73 94
37 92
37 75
33 92
40 82
98 93
41 97
64 4
21 3
5 54
69 86
43 15
57 59
69 18
42 10
62 14
40 22
72 12
17 42
17 34 2
23 -39 31
62 55 -30
12 -60 93
27 23 46
13 45 -82
48 23 -61
46 1 -99
14 34 62
26 -13 4
5 11 -22
42 -7 75
50 -85 42
21 -53 98
18 29 84
15 55 24
56 34 -84
47 65 -92
9 -84 73
10 23 38
24 66 -81

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 112ms
memory: 57776kb

input:

100
94361 94314
33869598 5185471
618720133 505036749
409602893 40833389
73363932 853969687
132417645 381351032
465347847 676007624
210787499 3355224
991034578 503557482
118882583 12886598
821718576 953581962
979222818 458179522
17341621 962353208
11732262 180321038
947467293 869555337
27442910 91111...

output:

790989612
671747997
0
437770386
293758108
417733173
876589319
754905430
511705067
4194304
908866994
0
362293000
268315788
810816358
587847598
378811885
673322235
478150607
897151370
331537435
714057465
262017639
527438203
922745986
484494985
318652554
331818541
767356752
601981094
34519446
0
5190730...

result:

ok 100 lines