QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397165 | #4391. Slayers Come | Diu | AC ✓ | 112ms | 57776kb | C++14 | 3.2kb | 2024-04-23 18:47:28 | 2024-04-23 18:47:29 |
Judging History
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