#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NU = 2100000000;
const ll INF = 0x3ffffffffffffff;
ll s0[300009], e0[300009];
ll s[300009], e[300009], ans[300009], stree[1<<20], etree[1<<20];
pair<ll, bool> resl[1009], resr[1009];
const int buc = 3;
struct Query{
int idx, a, b; //first query if b == -1
ll ta, tb;
};
void settree(int v, int l, int r){
if(l==r){
stree[v] = s[l];
etree[v] = e[l];
}
else{
int mid = (l+r)/2;
settree(2*v, l, mid);
settree(2*v+1, mid+1, r);
stree[v] = max(stree[2*v], stree[2*v+1]);
etree[v] = min(etree[2*v], etree[2*v+1]);
}
}
void update(int v, int l, int r, int idx){
if(l==r){
stree[v] = s[l];
etree[v] = e[l];
}
else{
int mid = (l+r)/2;
if(idx <= mid)
update(2*v, l, mid, idx);
else
update(2*v+1, mid+1, r, idx);
stree[v] = max(stree[2*v], stree[2*v+1]);
etree[v] = min(etree[2*v], etree[2*v+1]);
}
}
int mine_bound(int v, int l, int r, int s, ll B){
if(etree[v] >= B || r<s)
return NU;
if(l==r)
return l;
int mid=(l+r)/2, temp = mine_bound(2*v, l, mid, s, B);
if(temp==NU)
return mine_bound(2*v+1, mid+1, r, s, B);
return temp;
}
int maxs_bound(int v, int l, int r, int s, ll B){
if(stree[v] <= B || r<s)
return NU;
if(l==r)
return l;
int mid=(l+r)/2, temp = maxs_bound(2*v, l, mid, s, B);
if(temp==NU)
return maxs_bound(2*v+1, mid+1, r, s, B);
return temp;
}
pair<ll, ll> calculate(int a, int b, ll ta, ll tb){ //time leap, final time
ll cur = ta, ans = 0;
for(int i=a; i<=b; i++){
if(cur < s[i])
cur = s[i];
else if(cur > e[i]){
ans += cur - e[i];
cur = e[i];
}
}
if(cur > tb)
ans += cur - tb;
return make_pair(ans, cur);
}
void solve(int n, vector<Query> q){
int sz = q.size(), i, qr = n/buc;
if(n==0){
for(i=0; i<q.size(); i++){
if(q[i].b != -1){
ans[q[i].idx] = max(q[i].ta - q[i].tb, 0ll);
}
}
return;
}
settree(1, 1, n);
//for(i=1; i<=n; i++){
// printf("%d: s=%d e=%d\n", i, s[i], e[i]);
//}
for(i=1; i<qr; i++){
pair<ll, int> temp = calculate(buc*i, buc*(i+1), s[buc*i], -INF);
resl[i].first = temp.first;
resl[i].second = (temp.second == e[buc*(i+1)]);
temp = calculate(buc*i, buc*(i+1), e[buc*i], -INF);
resr[i].first = temp.first;
resr[i].second = (temp.second == e[buc*(i+1)]);
}
for(i=0; i<sz; i++){
if(q[i].b == -1){
s[q[i].a] = q[i].ta;
e[q[i].a] = q[i].tb;
update(1, 1, n, q[i].a);
int idx = q[i].a / buc;
if(idx > 0){
pair<ll, int> temp = calculate(buc*idx, buc*(idx+1), s[buc*idx], -INF);
resl[idx].first = temp.first;
resl[idx].second = (temp.second == e[buc*(idx+1)]);
temp = calculate(buc*idx, buc*(idx+1), e[buc*idx], -INF);
resr[idx].first = temp.first;
resr[idx].second = (temp.second == e[buc*(idx+1)]);
}
}
else{
int v = min(maxs_bound(1, 1, n, q[i].a, q[i].ta), mine_bound(1,1,n,q[i].a, q[i].ta));
/*printf("v=%d\n", v);
if(v!=NU)
printf("q[i].b=%d q[i].idx=%d q[i].a=%d ta=%lld s[v]=%lld e[v]=%lld v=%d\n", q[i].b,q[i].idx, q[i].a,q[i].ta,
s[v],e[v], v);*/
if(v==NU)
v=q[i].b + 1;
int ss = (q[i].a + buc - 1) / buc, ee = q[i].b / buc;
if(ss>=ee){
pair<ll, ll> temp = calculate(v, q[i].b, q[i].ta, q[i].tb);
ans[q[i].idx] = temp.first;
}
else{
pair<ll, ll> temp = calculate(v, ss*buc, q[i].ta, -INF);
ll cur = temp.first, now = temp.second;
bool flag = (temp.second==e[ss*buc]);
for(int j = ss; j < ee; j++){
if(!flag){
cur += resl[j].first;
flag = resl[j].second;
}
else{
cur += resr[j].first;
flag = resr[j].second;
}
}
cur += calculate(ee*buc, q[i].b, flag ? e[ee*buc] : s[ee*buc], q[i].tb).first;
ans[q[i].idx] = cur;
}
}
}
}
int main(){
int n, q, i, type, a, b;
ll ta, tb;
scanf("%d %d", &n, &q);
for(i=1; i<n; i++){
scanf("%lld %lld", &s0[i], &e0[i]);
s[i] = s0[i] - i;
e[i] = e0[i] - i - 1;
}
vector<Query> query(q), temp;
for(i=0; i<q; i++){
scanf("%d", &type);
if(type==1){
scanf("%d %lld %lld", &a, &ta, &tb);
query[i] = {i, a, -1, ta, tb};
}
else{
scanf("%d %lld %d %lld", &a, &ta, &b, &tb);
query[i] = {i, a, b, ta, tb};
}
}
n--;
temp.clear();
for(i=0; i<q; i++){
if(query[i].b == -1)
temp.push_back({i, query[i].a, query[i].b, query[i].ta-query[i].a, query[i].tb-query[i].a-1});
else if(query[i].a <= query[i].b)
temp.push_back({query[i].idx, query[i].a, query[i].b-1, query[i].ta - query[i].a, query[i].tb - query[i].b});
}
solve(n, temp);
n++;
for(i=1; i<n; i++){
s[i] = s0[n-i] - i;
e[i] = e0[n-i] - i - 1;
}
temp.clear();
for(i=0; i<q; i++){
if(query[i].b == -1)
temp.push_back({i, n-query[i].a, -1, query[i].ta-(n-query[i].a), query[i].tb-(n-query[i].a)-1});
else if(query[i].a > query[i].b)
temp.push_back({query[i].idx, n-query[i].a+1, n-query[i].b, query[i].ta - (n - query[i].a + 1), query[i].tb - (n - query[i].b) - 1});
}
n--;
solve(n, temp);
for(i=0; i<q; i++){
if(query[i].b != -1)
printf("%lld\n", ans[query[i].idx]);
}
/*while(q--){
scanf("%d", &type);
if(type==1){
scanf("%d %lld %lld", &i, &ta, &tb);
s[i] = ta - i;
e[i] = tb - i - 1;
s2[i] = ta + i;
e2[i] = tb + i - 1;
}
else{
scanf("%d %lld %d %lld", &a, &ta, &b, &tb);
if(a<b){
ta -= a;
tb -= b;
ll cur = ta, ans = 0;
for(i=a; i<b; i++){
if(cur < s[i])
cur = s[i];
else if(cur > e[i]){
ans += cur - e[i];
cur = e[i];
}
}
if(cur > tb)
ans += cur - tb;
printf("%lld\n", ans);
}
else{
ta += a-1;
tb += b-1;
ll cur = ta, ans = 0;
for(i=a-1; i>=b; i--){
if(cur < s2[i])
cur = s2[i];
else if(cur > e2[i]){
ans += cur - e2[i];
cur = e2[i];
}
}
if(cur > tb)
ans += cur - tb;
printf("%lld\n", ans);
}
}
}*/
return 0;
}
Compilation message
timeleap.cpp: In function 'void solve(int, std::vector<Query>)':
timeleap.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(i=0; i<q.size(); i++){
| ~^~~~~~~~~
timeleap.cpp:128:38: warning: unused variable 'now' [-Wunused-variable]
128 | ll cur = temp.first, now = temp.second;
| ^~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | scanf("%lld %lld", &s0[i], &e0[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
timeleap.cpp:159:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | scanf("%d %lld %lld", &a, &ta, &tb);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:163:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | scanf("%d %lld %d %lld", &a, &ta, &b, &tb);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3024 ms |
52756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
