oj.uz

Submission #617201

# Submission time Handle Problem Language Result Execution time Memory
617201 2022-08-01T09:34:50 Z 이동현(#8506) Sweeping (JOI20_sweeping) C++17
11 / 100
 1029 ms 106504 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Seg{
    int n;
    vector<int> tr, lazy;

    Seg(){}
    Seg(int n):n(n + 4){
        tr.resize(n * 4 + 4, (int)2e9);
        lazy.resize(n * 4, -1);
    }

    void push(int x, int s, int e, int ps, int pe, int val){
        if(pe < s || ps > e || ps > pe){
            return;
        }

        if(ps <= s && pe >= e){
            tr[x] = val;
            lazy[x] = val;

            return;
        }

        if(lazy[x] != -1){
            tr[x * 2] = lazy[x * 2] = lazy[x];
            tr[x * 2 + 1] = lazy[x * 2 + 1] = lazy[x];

            lazy[x] = -1;
        }

        int m = s + e >> 1;
        push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);

        tr[x] = min(tr[x * 2], tr[x * 2 + 1]);
    }

    int get(int x, int s, int e, int fs, int fe, int val){
        if(fe < s || fs > e || fs > fe) return (int)1e9;

        if(s == e){
            if(tr[x] <= val){
                return s;
            }
            return (int)1e9;
        }

        if(lazy[x] != -1){
            tr[x * 2] = lazy[x * 2] = lazy[x];
            tr[x * 2 + 1] = lazy[x * 2 + 1] = lazy[x];

            lazy[x] = -1;
        }

        int m = s + e >> 1;
        if(tr[x * 2] <= val){
            return get(x * 2, s, m, fs, fe, val);
        }
        return get(x * 2 + 1, m + 1, e, fs, fe, val);
    }

    int get2(int x, int s, int e, int pos){
        if(s == e){
            return tr[x];
        }

        if(lazy[x] != -1){
            tr[x * 2] = lazy[x * 2] = lazy[x];
            tr[x * 2 + 1] = lazy[x * 2 + 1] = lazy[x];

            lazy[x] = -1;
        }

        int m = s + e >> 1;
        if(pos <= m) return get2(x * 2, s, m, pos);
        return get2(x * 2 + 1, m + 1, e, pos);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> p(m);
    vector<int> st(m);

    for(int i = 0; i < m; ++i){
        p[i].resize(2);
        cin >> p[i][0] >> p[i][1];
    }

    Seg tr[2];
    tr[0] = tr[1] = Seg(m + 4);

    for(int i = 0; i < m; ++i){
        tr[0].push(1, 0, m - 1, i, i, p[i][1]);
        tr[1].push(1, 0, m - 1, m - i - 1, m - i - 1, p[i][0]);
    }

    while(q--){
        int t; cin >> t;

        if(t == 1){
            int x; cin >> x; --x;

            cout << tr[1].get2(1, 0, m - 1, m - x - 1) << ' ' << tr[0].get2(1, 0, m - 1, x) << '\n';
        }
        else if(t == 2){
            int l; cin >> l;

            int p1 = tr[0].get(1, 0, m - 1, 0, m - 1, l);
            int p2 = tr[1].get(1, 0, m - 1, 0, m - 1, n - l);

            tr[1].push(1, 0, m - 1, p2, m - p1 - 1, n - l);
        }
        else{
            int l; cin >> l;

            int p1 = tr[1].get(1, 0, m - 1, 0, m - 1, l);
            int p2 = tr[0].get(1, 0, m - 1, 0, m - 1, n - l);

            tr[0].push(1, 0, m - 1, p2, m - p1 - 1, n - l);
        }
    }

    return 0;
}

Compilation message

sweeping.cpp: In member function 'void Seg::push(long long int, long long int, long long int, long long int, long long int, long long int)':
sweeping.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = s + e >> 1;
      |                 ~~^~~
sweeping.cpp: In member function 'long long int Seg::get(long long int, long long int, long long int, long long int, long long int, long long int)':
sweeping.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int m = s + e >> 1;
      |                 ~~^~~
sweeping.cpp: In member function 'long long int Seg::get2(long long int, long long int, long long int, long long int)':
sweeping.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 725 ms 99012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1029 ms 104172 KB Output is correct
2 Correct 953 ms 106412 KB Output is correct
3 Correct 918 ms 106024 KB Output is correct
4 Correct 992 ms 106364 KB Output is correct
5 Correct 1025 ms 106400 KB Output is correct
6 Correct 957 ms 106504 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1029 ms 104172 KB Output is correct
2 Correct 953 ms 106412 KB Output is correct
3 Correct 918 ms 106024 KB Output is correct
4 Correct 992 ms 106364 KB Output is correct
5 Correct 1025 ms 106400 KB Output is correct
6 Correct 957 ms 106504 KB Output is correct
7 Incorrect 881 ms 106496 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -