#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);
}
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:98: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:101: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 |
Incorrect |
9 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2343 ms |
299468 KB |
Output is correct |
| 2 |
Correct |
1848 ms |
288748 KB |
Output is correct |
| 3 |
Correct |
1853 ms |
292128 KB |
Output is correct |
| 4 |
Correct |
2252 ms |
283512 KB |
Output is correct |
| 5 |
Correct |
1954 ms |
304248 KB |
Output is correct |
| 6 |
Correct |
1882 ms |
299164 KB |
Output is correct |
| 7 |
Correct |
1963 ms |
308472 KB |
Output is correct |
| 8 |
Correct |
2017 ms |
320876 KB |
Output is correct |
| 9 |
Correct |
1917 ms |
285560 KB |
Output is correct |
| 10 |
Correct |
1915 ms |
307272 KB |
Output is correct |
| 11 |
Correct |
1924 ms |
304760 KB |
Output is correct |
| 12 |
Correct |
1997 ms |
325752 KB |
Output is correct |
| 13 |
Correct |
2029 ms |
330652 KB |
Output is correct |
| 14 |
Correct |
10 ms |
16768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
