oj.uz

Submission #893363

# Submission time Handle Problem Language Result Execution time Memory
893363 2023-12-27T03:20:46 Z vjudge1 Inspections (NOI23_inspections) C++17
0 / 100
 1 ms 6744 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define fi first
#define se second

using namespace std;
const int maxn = 2e5 + 5;
int n, m,q;
pair <int, int> a[maxn];
int id[maxn];
long long s[maxn], s1[maxn];
set <pair <int, int>> st;
vector <pair <int, int>> vt;
vector <pair <long long, int>> v;
long long f[maxn];

bool cmp(int i, int j) {
    return s[i]> s[j];
}

int main() {
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        cin >> a[i].fi >> a[i].se;
        s1[i] = s1[i - 1] + (a[i].se - a[i].fi + 1);
    }
    for(int i = 1; i <= q; ++i) cin >> s[i];
    for(int i = 1; i <= q; ++i) id[i] = i;
    st.insert({1, 0});
    st.insert({n + 1, 0});
    sort(id + 1, id + q + 1, cmp);
    for(int i = 1; i <= m; ++i) {
        vt.clear();
        auto it = st.upper_bound({a[i].fi, 0});
        --it;
        int x = 0;
        int y = 0;
        int dx = 0;
        int dy = 0;
        for(it; it != st.end(); ++it) {
            auto r = (*it);
            if(r.fi < a[i].fi) {
                x = r.fi;
                dx = r.se;
            }
            else if(r.fi >= a[i].se + 1) {
                if(r.fi == a[i].se + 1) break;
                y = r.fi - 1;
                dy = (*(--it)).se;
                break;
            }
            auto it1 = it;
            auto nxt = *(++it1);
            vt.push_back(r);
            int d = r.se;
            if(d == 0) continue;
            if(r.fi < a[i].fi) {
                v.push_back({s1[i - 1] - s1[d] + a[d].se - a[i].fi + 1, min(nxt.fi, a[i].se + 1) - a[i].fi});
            }
            else {
                v.push_back({s1[i - 1] - s1[d] + r.fi - a[i].fi + a[d].se - r.fi + 1, min(nxt.fi, a[i].se + 1) - r.fi});
            }

        }
        for(auto j : vt) {
            st.erase(j);
        }
        if(x) st.insert({x, dx});
        if(y) st.insert({a[i].se + 1, dy});
        st.insert({a[i].fi, i});

    }
    sort(v.begin(), v.end());
    long long res = 0;
    for(int i1 = 1; i1 <= q; ++i1) {
        int i = id[i1];
        while(!v.empty() && v.back().fi > s[i]) {
            res += v.back().se;
            v.pop_back();
        }
        f[i] = res;
    }
    for(int i = 1; i <= q; ++i) cout << f[i] << ' ';

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:13: warning: statement has no effect [-Wunused-value]
   44 |         for(it; it != st.end(); ++it) {
      |             ^~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 23.0

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