#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int OFF = (1 << 19);
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 500;
const int LOG = 20;
pii T[2 * OFF][2];
int n, q;
inline pii mrg(pii A, pii B){
return {max(A.X, B.X), min(A.Y, B.Y)};
}
void update(int i, int j, pii nw){
T[i + OFF][j] = nw;
for(i = (i + OFF) / 2 ; i ; i /= 2)
T[i][j] = mrg(T[2 * i][j], T[2 * i + 1][j]);
}
int q_gr, q_x, q_j;
int desnoo(int i, int a, int b){
//printf("i = %d a = %d b = %d q_gr = %d q_x = %d q_j = %d\n", i, a, b, q_gr, q_x, q_j);
if(b < q_gr || (T[i][q_j].X <= q_x && q_x <= T[i][q_j].Y))
return -1;
if(a == b) return a;
int L = desnoo(2 * i, a, (a + b) / 2);
if(L != -1)
return L;
return desnoo(2 * i + 1, (a + b) / 2 + 1, b);
}
inline int desno(int gdje, int kol, int j){
q_gr = gdje; q_x = kol; q_j = j;
return desnoo(1, 0, OFF - 1);
}
int par[2 * N][2][LOG], LL[N], RR[N], L[N][2], R[N][2];
ll cst[2 * N][2][LOG];
int vis[2 * N][2];
inline int get_pos(int x){
if(x == 2 * n) return n;
return x % n;
}
int main(){
for(int i = 0;i < 2 * OFF;i++)
T[i][0] = {-INF, INF}, T[i][1] = {-INF, INF};
scanf("%d%d", &n, &q); n--;
for(int i = 0;i < n;i++){
scanf("%d%d", LL + i, RR + i); RR[i]--;
L[i][0] = LL[i] - i, R[i][0] = RR[i] - i;
L[n - i - 1][1] = LL[i] - (n - i - 1);
R[n - i - 1][1] = RR[i] - (n - i - 1);
}
if(n <= 1000 && q <= 1000){
for(;q--;){
int ty; scanf("%d", &ty);
if(ty == 1){
int i, a, b; scanf("%d%d%d", &i, &a, &b); i--;
L[i][0] = a - i, R[i][0] = b - i;
L[n - i - 1][1] = a - (n - i - 1);
R[n - i - 1][1] = b - (n - i - 1);
continue;
}
int st, en, v_st, v_en;
scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
int k = (st > en);
if(k){
st = n - st; en = n - en;
}
v_st -= st; v_en -= en;
ll ans = 0;
int sad = v_st, cur = st;
for(;cur < en;cur++){
if(L[cur][k] > sad)
sad = L[cur][k];
if(R[cur][k] < sad){
ans += (ll)(sad - R[cur][k]);
sad = R[cur][k];
}
}
if(sad > v_en)
ans += sad - v_en;
printf("%lld\n", ans);
}
return 0;
}
for(int k = 0;k < 2;k++){
for(int i = 0;i < n;i++){
update(i, k, {L[i][k], R[i][k]});
vis[i][k] = L[i][k]; vis[i + n][k] = R[i][k];
}
update(n, k, {INF, -INF});
for(int i = 0;i < 2 * n;i++){
par[i][k][0] = desno(i % n, vis[i][k], k);
if(par[i][k][0] == n){
par[i][k][0] += n;
}
else if(vis[i][k] > R[par[i][k][0]][k]){
cst[i][k][0] = vis[i][k] - R[par[i][k][0] % n][k];
par[i][k][0] += n;
}
//printf("%d --> %d\n", i, par[i][k][0]);
}
//printf("tu sam\n");
par[2 * n][k][0] = 2 * n;
for(int j = 1;j < LOG;j++){
par[2 * n][k][j] = 2 * n;
for(int i = 0;i < 2 * n;i++){
par[i][k][j] = par[par[i][k][j - 1]][k][j - 1];
cst[i][k][j] = cst[i][k][j - 1] + cst[par[i][k][j - 1]][k][j - 1];
}
}
//printf("gotov precompute\n");
}
for(;q--;){
int ty; scanf("%d", &ty);
if(ty == 1) return 0;
int st, en, v_st, v_en;
scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
int k = (st > en);
if(k){
st = n - st; en = n - en;
}
v_st -= st; v_en -= en;
//printf("st time = %d en time = %d\n", v_st, v_en);
int cur = desno(st, v_st, k);
//printf("vis %d\n", R[cur][k]);
//printf("cur = %d\n", cur);
if(cur >= en){
printf("%lld\n", max((ll)v_st - v_en, 0LL));
continue;
}
ll ans = 0;
if(v_st > R[cur][k]){
ans += v_st - R[cur][k];
cur += n;
}
for(int i = LOG - 1;i >= 0;i--){
if(get_pos(par[cur][k][i]) < en){
ans += cst[cur][k][i];
cur = par[cur][k][i];
}
}
//printf("cur = %d\n", cur);
//printf("ans: %lld\n", ans);
//printf("vis : %d krj : %d\n", vis[cur][k], v_en);
ans += max((ll)vis[cur][k] - v_en, 0LL);
printf("%lld\n", ans);
}
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q); n--;
~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", LL + i, RR + i); RR[i]--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int ty; scanf("%d", &ty);
~~~~~^~~~~~~~~~~
timeleap.cpp:73:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int i, a, b; scanf("%d%d%d", &i, &a, &b); i--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:133:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int ty; scanf("%d", &ty);
~~~~~^~~~~~~~~~~
timeleap.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &st, &v_st, &en, &v_en); st--; en--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16768 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
16768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1921 ms |
289404 KB |
Output is correct |
| 2 |
Correct |
1833 ms |
273512 KB |
Output is correct |
| 3 |
Correct |
1847 ms |
276880 KB |
Output is correct |
| 4 |
Correct |
2009 ms |
268400 KB |
Output is correct |
| 5 |
Correct |
2311 ms |
288792 KB |
Output is correct |
| 6 |
Correct |
1960 ms |
283800 KB |
Output is correct |
| 7 |
Correct |
2541 ms |
293028 KB |
Output is correct |
| 8 |
Correct |
2057 ms |
304944 KB |
Output is correct |
| 9 |
Correct |
2086 ms |
270384 KB |
Output is correct |
| 10 |
Correct |
1999 ms |
291952 KB |
Output is correct |
| 11 |
Correct |
1952 ms |
289240 KB |
Output is correct |
| 12 |
Correct |
2054 ms |
309936 KB |
Output is correct |
| 13 |
Correct |
2037 ms |
314632 KB |
Output is correct |
| 14 |
Correct |
12 ms |
16768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16768 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
16768 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
