oj.uz

Submission #1030730

# Submission time Handle Problem Language Result Execution time Memory
1030730 2024-07-22T09:13:38 Z 김은성(#10955) Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 3000 ms 524288 KB 
#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==1){
        for(i=0; i<q.size(); i++){
            if(q[i].b != -1){
                ans[q[i].idx] = max(q[i].tb - q[i].ta, 0ll);
            }
        }
    }
    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;
            pair<ll, ll> temp = calculate(v, q[i].b, q[i].ta, q[i].tb);
            ans[q[i].idx] = temp.first;
        }
    }
}
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: In function 'int main()':
timeleap.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%lld %lld", &s0[i], &e0[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf("%d", &type);
      |         ~~~~~^~~~~~~~~~~~~
timeleap.cpp:138:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |             scanf("%d %lld %lld", &a, &ta, &tb);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d %lld %d %lld", &a, &ta, &b, &tb);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 1 ms 12636 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 3 ms 12636 KB Output is correct
12 Correct 2 ms 12872 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12632 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 2 ms 12636 KB Output is correct
22 Correct 2 ms 12636 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 2 ms 12636 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12632 KB Output is correct
31 Correct 2 ms 12632 KB Output is correct
32 Correct 3 ms 12632 KB Output is correct
33 Correct 2 ms 12632 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 2 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 3 ms 12636 KB Output is correct
40 Correct 2 ms 12632 KB Output is correct
41 Runtime error 227 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 46520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 1 ms 12636 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 3 ms 12636 KB Output is correct
12 Correct 2 ms 12872 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12636 KB Output is correct
15 Correct 2 ms 12632 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 2 ms 12636 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 2 ms 12636 KB Output is correct
22 Correct 2 ms 12636 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 2 ms 12636 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12632 KB Output is correct
31 Correct 2 ms 12632 KB Output is correct
32 Correct 3 ms 12632 KB Output is correct
33 Correct 2 ms 12632 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 2 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 3 ms 12636 KB Output is correct
40 Correct 2 ms 12632 KB Output is correct
41 Runtime error 227 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -