oj.uz

답안 #796807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796807 2023-07-28T18:42:13 Z RushB Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 404 ms 90576 KB 
//besmellah
//mage mikhad chi beshe?
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 
#define int long long
const int64_t INF = 1ll << 60;
const int N = 3e5 + 50;
int n, q, A[N], B[N], C[N], D[N], P[N], t[N], L[N], R[N], query_ans[N];

struct node {
        int mxl, mnr, fil, fir, ansl, ansr, locl, locr;
};
int dist(int l, int r) {
        return max(r - l, 0ll);
}
void calc(node x, int l, int &rel, int &reans) {
        if (x.mxl <= x.mnr) {
                rel = min(max(l, x.mxl), x.mnr);
                reans += dist(rel, l);
        }
        else {
                int dl = dist(x.fil, l) + x.ansl;
                int dr = dist(x.fir, l) + x.ansr;
                if (dl < dr) {
                        reans += dl;
                        rel = x.locl;
                }
                else {
                        reans += dr; 
                        rel = x.locr;
                }
        }
}

node operator +(node l, node r) {
        node R;
        R.mxl = max(l.mxl, r.mxl);
        R.mnr = min(l.mnr, r.mnr);
        if (R.mxl <= R.mnr) {
                R.ansl = R.ansr = 0;
                R.locl = R.mxl;
                R.locr = R.mnr;
                R.fil = R.mxl;
                R.fir = R.mnr;
                return R;
        }
        R.fil = l.fil;
        R.fir = l.fir;
        R.ansl = R.ansr = 0;
        calc(r, l.locl, R.locl, R.ansl);
        calc(r, l.locr, R.locr, R.ansr);
        R.ansl += l.ansl;
        R.ansr += l.ansr;
        return R;
}
node seg[N << 2];

//int mxl, mnr, fil, fir, ansl, ansr, locl, locr;
void build(int v, int l, int r) {
        if (l + 1 == r) {
                seg[v] = {L[l], R[l], L[l], R[l], 0, 0, L[l], R[l]};
                return;
        }
        int m = l + r >> 1;
        build(v << 1, l, m);
        build(v << 1 | 1, m, r);
        seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
void update(int v, int l, int r, int ind, int L, int R) {
        if (l + 1 == r) {
                seg[v] = {L, R, L, R, 0, 0, L, R};
                return;
        }
        int m = l + r >> 1;
        if (ind < m)
                update(v << 1, l, m, ind, L, R);
        else
                update(v << 1 | 1, m, r, ind, L, R);
        seg[v] = seg[v << 1] + seg[v << 1 | 1];
}
//void calc(node x, int l, int &rel, int &reans) {
void get(int v, int l, int r, int L, int R, int &time, int &re) {
        if (L <= l && r <= R) {
                calc(seg[v], time, time, re);
                return;
        }
        int m = l + r >> 1;
        if (R <= m)
                get(v << 1, l, m, L, R, time, re);
        else if (L >= m)
                get(v << 1 | 1, m, r, L, R, time, re);
        else {
                get(v << 1, l, m, L, R, time, re);
                get(v << 1 | 1, m, r, L, R, time, re);
        }
}

void solve() {
        FOR(i, 1, n) {
                L[i] -= i;
                R[i] -= i + 1;
        }
        build(1, 1, n);
        FOR(i, 0, q) {
                B[i] -= (t[i] == 1 ? P[i] : A[i]);
                D[i] -= (t[i] == 1 ? P[i] + 1 : C[i]);
        }
        FOR(i, 0, q) {
                if (t[i] == 1) {
                       update(1, 1, n, P[i], B[i], D[i]); 
                }
                else if (C[i] > A[i]) {
                        int time = B[i];
                        get(1, 1, n, A[i], C[i], time, query_ans[i]);
                        query_ans[i] += dist(D[i], time);
                }
                else if (C[i] == A[i])
                        query_ans[i] = dist(D[i], B[i]);
        }
        FOR(i, 1, n) {
                L[i] += i;
                R[i] += i + 1;
        }
        FOR(i, 0, q) {
                B[i] += (t[i] == 1 ? P[i] : A[i]);
                D[i] += (t[i] == 1 ? P[i] + 1 : C[i]);
        }
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n >> q;
        FOR(i, 1, n)
                cin >> L[i] >> R[i];
        FOR(i, 0, q) {
                cin >> t[i];
                if (t[i] == 1) {
                        cin >> P[i] >> B[i] >> D[i];
                }
                else {
                        cin >> A[i] >> B[i] >> C[i] >> D[i];
                }
        }
        solve();
        reverse(L + 1, L + n);
        reverse(R + 1, R + n);
        
        FOR(i, 0, q) {
                if (t[i] == 1) {
                        P[i] = n - P[i];
                }
                else {
                        A[i] = n + 1 - A[i];
                        C[i] = n + 1 - C[i];
                }
        }
        solve();

        FOR(i, 0, q)
                if (t[i] == 2) {
                        cout << query_ans[i] << '\n';
                }

        return 0;
}
//19:33:34

Compilation message

timeleap.cpp: In function 'void build(long long int, long long int, long long int)':
timeleap.cpp:65:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int m = l + r >> 1;
      |                 ~~^~~
timeleap.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:75:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int m = l + r >> 1;
      |                 ~~^~~
timeleap.cpp: In function 'void get(long long int, long long int, long long int, long long int, long long int, long long int&, long long int&)':
timeleap.cpp:88:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 404 ms 90576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -