#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAXN 300005
typedef pair<long long, int> pi;
const int INF=1e9;
int N, rn;
int L[MAXN], R[MAXN];
int T[MAXN], A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int LL[2*MAXN], RR[2*MAXN];
int lmax[6*MAXN], rmin[6*MAXN];
int root[800];
pi dp[4*MAXN];
void updseg(int x, int idx, int l, int r){
if(l==r){
lmax[idx]=l;
rmin[idx]=l;
}
else{
int m=(l+r)/2;
if(x<=m) updseg(x, idx*2, l, m);
else updseg(x, idx*2+1, m+1, r);
lmax[idx]=LL[lmax[idx*2]]>=LL[lmax[idx*2+1]]?lmax[idx*2]:lmax[idx*2+1];
rmin[idx]=RR[rmin[idx*2]]<=RR[rmin[idx*2+1]]?rmin[idx*2]:rmin[idx*2+1];
}
}
int gbigl(int x, int y, int idx, int l, int r){
//printf("*x=%d, y=%d, l=%d, r=%d\n", x, y, l, r);
if(LL[lmax[idx]]<y) return r+1;
if(l==r) return l;
int m=(l+r)/2;
if(x>m) return gbigl(x, y, idx*2+1, m+1, r);
int t=gbigl(x, y, idx*2, l, m);
return t==m+1?gbigl(x, y, idx*2+1, m+1, r):t;
}
int gsmar(int x, int y, int idx, int l, int r){
if(RR[rmin[idx]]>y) return r+1;
if(l==r) return l;
int m=(l+r)/2;
if(x>m) return gsmar(x, y, idx*2+1, m+1, r);
int t=gsmar(x, y, idx*2, l, m);
return t==m+1?gsmar(x, y, idx*2+1, m+1, r):t;
}
pi move(int x1, int x2, int y1){
int x=x1, y=y1<2*N?LL[y1]:RR[y1-2*N];
pi ans=make_pair(0, y1);
while(x<x2){
x++;
if(LL[x]>y){
ans.second=x;
y=LL[x];
}
else if(RR[x]<y){
ans.first+=y-RR[x];
ans.second=x+2*N;
y=RR[x];
}
}
return ans;
}
int gr(int x){
int r=0;
while(r<rn&&root[r+1]<=x) r++;
return r;
}
void update(int x, int l, int r){
//printf("[%d %d %d]\n", x, l, r);
LL[x]=l;
RR[x]=r;
updseg(x, 1, 0, 2*N-3);
r=gr(x);
if(r>0) for(int i=root[r-1]; i<root[r]; i++) for(int j=i; j<=i+2*N; j+=2*N)
dp[j]=move(root[r], root[r+1], j);
}
void print(){
for(int i=0; i<2*N-2; i++) printf("%d ", LL[i]);
printf("\n");
for(int i=0; i<2*N-2; i++) printf("%d ", RR[i]);
printf("\n[%d %d]\n", lmax[1], rmin[1]);
for(int i=0; i<rn-1; i++) for(int j=root[i]; j<root[i+1]; j++) for(int k=j; k<=j+2*N; k+=2*N)
dp[k]=move(root[i+1], root[i+2], k);
for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second);
printf("\n");
}
int main(){
int Q;
//freopen("input.txt", "r", stdin);
scanf("%d%d", &N, &Q);
for(int i=0; i<N-1; i++) scanf("%d%d", L+i, R+i);
for(int i=0; i<Q; i++){
scanf("%d%d%d%d", T+i, A+i, B+i, C+i);
if(T[i]==2) scanf("%d", D+i);
}
for(int i=0; i<N-1; i++){
LL[i]=L[i]-i;
RR[i]=R[i]-i-1;
updseg(i, 1, 0, 2*N-3);
LL[2*N-3-i]=L[i]+i;
RR[2*N-3-i]=R[i]+i-1;
updseg(2*N-3-i, 1, 0, 2*N-3);
}
for(rn=1; (rn+1)*(rn+1)<=2*N-3; rn++);
root[0]=0;
for(int i=1; i<=rn; i++) root[i]=root[i-1]+(2*N-3)/rn+(i<=(2*N-3)%rn?1:0);
//for(int i=0; i<=rn; i++) printf("%d ", root[i]);
//printf("\n");
//print();
for(int i=0; i<Q; i++){
if(T[i]==1){
update(A[i]-1, B[i]-A[i]+1, C[i]-A[i]);
update(2*N-2-A[i], B[i]+A[i]-1, C[i]+A[i]-2);
//print();
}
else{
int x1, y1, x2, y2;
if(A[i]<C[i]){
x1=A[i]-1;
y1=B[i]-A[i]+1;
x2=C[i]-2;
y2=D[i]-C[i]+1;
}
else{
x1=2*N-1-A[i];
y1=B[i]+A[i]-2;
x2=2*N-2-C[i];
y2=D[i]+C[i]-2;
}
//printf("x1=%d, y1=%d, x2=%d, y2=%d\n", x1, y1, x2, y2);
int lb=gbigl(x1, y1+1, 1, 0, 2*N-3), rs=gsmar(x1, y1-1, 1, 0, 2*N-3);
//printf("lb=%d, rs=%d\n", lb, rs);
int k=lb<rs?lb:rs+2*N, x3=min(lb, rs);
long long ans=lb<rs?0:y1-RR[rs];
if(x3>x2){
printf("%d\n", y1<y2?0:y1-y2);
continue;
}
int r1=gr(x3), r2=gr(x2);
if(r1==r2){
pi p=move(x3, x2, k);
int y=p.second<2*N?LL[p.second]:RR[p.second-2*N];
//printf("x3=%d, x2=%d, k=%d, p=(%d, %d), y=%d\n", x3, x2, k, p.first, p.second, y);
printf("%lld\n", ans+(y>y2?y-y2:0));
continue;
}
pi p=move(x3, root[r1+1], k);
//printf("r1=%d, r2=%d, p=(%d, %d)\n", r1, r2, p.first, p.second);
ans+=p.first;
for(int j=r1+1; j<r2-1; j++){
p=move(root[j], root[j+1], p.second);
ans+=p.first;
}
p=move(root[r2], x2, p.second);
//printf("p=(%d, %d)\n", p.first, p.second);
ans+=p.first;
int y=p.second<2*N?LL[p.second]:RR[p.second-2*N];
printf("%lld\n", ans+(y>y2?y-y2:0));
}
}
return 0;
}
Compilation message
timeleap.cpp: In function 'void print()':
timeleap.cpp:93:125: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second);
~~~~~~~~~~~~~~~~~ ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:102:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N-1; i++) scanf("%d%d", L+i, R+i);
~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", T+i, A+i, B+i, C+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:105:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if(T[i]==2) scanf("%d", D+i);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
313 ms |
31324 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
