oj.uz

Submission #616689

# Submission time Handle Problem Language Result Execution time Memory
616689 2022-08-01T06:14:25 Z 이동현(#8506) Sweeping (JOI20_sweeping) C++17
10 / 100
 1965 ms 188412 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

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

    void push(int x, int s, int e, int pos, int val){
        if(s == e){
            tr[x] = val;

            return;
        }

        int m = s + e >> 1;
        if(pos <= m){
            push(x * 2, s, m, pos, val);
        }
        else{
            push(x * 2 + 1, m + 1, e, pos, val);
        }

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

    int get(int x, int s, int e, int fs, int fe){
        if(fe < s || fs > e) return -1;
        if(fs <= s && fe >= e){
            return tr[x];
        }

        int m = s + e >> 1;
        return max(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

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];
    }

    vector<vector<int>> que;

    for(int qq = 1; qq <= q; ++qq){
        int t; cin >> t;

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

            que.push_back({p[x][1], x, qq});
        }
        else if(t == 2){
            int l; cin >> l;

            que.push_back({l, qq + (int)1e9});
        }
        else{
            int x, y; cin >> x >> y;

            p.push_back({x, y});
            st.push_back(qq);
        }
    }

    sort(que.begin(), que.end());
    reverse(que.begin(), que.end());

    vector<vector<int>> ans(q + 1);
    Seg tree(q + 4);

    for(int i = 0; i < (int)que.size(); ++i){
        if((int)que[i].size() == 3){
            ans[que[i][2]] = {max(tree.get(1, 0, q, st[que[i][1]], que[i][2]), p[que[i][1]][0]), p[que[i][1]][1]};
        }
        else{
            que[i][1] -= (int)1e9;
            
            tree.push(1, 0, q, que[i][1], n - que[i][0]);
        }
    }

    for(int i = 1; i <= q; ++i){
        if((int)ans[i].size() == 2){
            cout << ans[i][0] << ' ' << ans[i][1] << '\n';
        }
    }

    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)':
sweeping.cpp:21:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         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)':
sweeping.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1894 ms 169904 KB Output is correct
2 Correct 1936 ms 188316 KB Output is correct
3 Correct 1846 ms 188224 KB Output is correct
4 Correct 1796 ms 187152 KB Output is correct
5 Correct 1965 ms 187752 KB Output is correct
6 Correct 1734 ms 188156 KB Output is correct
7 Correct 1823 ms 188412 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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