oj.uz

Submission #954161

# Submission time Handle Problem Language Result Execution time Memory
954161 2024-03-27T10:50:25 Z browntoad Inspections (NOI23_inspections) C++14
100 / 100
 243 ms 30788 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
 
const ll maxn = 1e6+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
 

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}
 
template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}

int n, m, q;
vector<pii> tag; // lazy tag to modify suffix
 
multiset<ppi> st;
 
set<ppi> ::iterator rep(set<ppi> ::iterator it, int L, int R, int v){
    ppi cur = (*it);
    int l = cur.f.f;
    int r = cur.f.s;
    //cout<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<cur.s<<' '<<v<<endl;
    if (r < L || l > R) return next(it);
    if (l < L && r > R){
        tag.pb({v-(cur.s+L-l)-1, R-L+1});
        st.insert({{l, L-1}, cur.s});
        st.insert({{R+1, r}, cur.s+R+1-l});
        return st.erase(it);
    }
    if (l < L){
        //cout<<"toad"<<endl;
        tag.pb({v-(cur.s+L-l)-1, r-L+1});
        st.insert({{l, L-1}, cur.s});
        return st.erase(it);
    }
    if (r > R){
        tag.pb({v-(cur.s-(l-L))-1, R-l+1});
        st.insert({{R+1, r}, cur.s+R+1-l});
        return st.erase(it);
    }
 
    tag.pb({v-(cur.s-(l-L))-1, r-l+1});
    return st.erase(it);
}
signed main(){
    IOS();
    cin>>n>>m>>q;
    int cval = 0;
    REP(i, m){
        int L, R; cin>>L>>R;
        if (SZ(st) > 0){
            auto tt = st.lower_bound({{L+1, 0}, 0});
            if (tt != st.begin()){
                tt = prev(tt);
            }
            while(tt != st.end() && (*tt).f.f <= R){
                tt = rep(tt, L, R, cval);
            }
        }
        st.insert({{L, R}, cval});
 
        cval += R-L+1;
    }
    sort(ALL(tag), greater<pii> ());
 
    vector<pii> quer(q);
    REP(i, q){
        cin>>quer[i].f;
        quer[i].s = i;
    }
    vector<int> ans(q);
    sort(ALL(quer), greater<pii> ());
    int ptr = 0, woo = 0;
    REP(i, q){
        while(ptr < SZ(tag) && tag[ptr].f >= quer[i].f){
            woo += tag[ptr].s;
            ptr++;
        }
 
        ans[quer[i].s] = woo;
    }
    REP(i, q) cout<<ans[i]<<' ';
    cout<<endl;
 
}
/*
5 3 7
1 3
3 5
2 3
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 43 ms 7252 KB Output is correct
14 Correct 39 ms 7004 KB Output is correct
15 Correct 40 ms 7256 KB Output is correct
16 Correct 43 ms 7248 KB Output is correct
17 Correct 41 ms 6996 KB Output is correct
18 Correct 40 ms 6992 KB Output is correct
19 Correct 43 ms 7392 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 43 ms 7196 KB Output is correct
4 Correct 44 ms 7768 KB Output is correct
5 Correct 128 ms 17584 KB Output is correct
6 Correct 122 ms 16036 KB Output is correct
7 Correct 94 ms 13500 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 43 ms 7252 KB Output is correct
14 Correct 39 ms 7004 KB Output is correct
15 Correct 40 ms 7256 KB Output is correct
16 Correct 43 ms 7248 KB Output is correct
17 Correct 41 ms 6996 KB Output is correct
18 Correct 40 ms 6992 KB Output is correct
19 Correct 43 ms 7392 KB Output is correct
20 Correct 42 ms 8276 KB Output is correct
21 Correct 40 ms 7404 KB Output is correct
22 Correct 41 ms 8272 KB Output is correct
23 Correct 39 ms 7504 KB Output is correct
24 Correct 40 ms 6996 KB Output is correct
25 Correct 43 ms 7804 KB Output is correct
26 Correct 42 ms 8280 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 43 ms 7252 KB Output is correct
14 Correct 39 ms 7004 KB Output is correct
15 Correct 40 ms 7256 KB Output is correct
16 Correct 43 ms 7248 KB Output is correct
17 Correct 41 ms 6996 KB Output is correct
18 Correct 40 ms 6992 KB Output is correct
19 Correct 43 ms 7392 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 352 KB Output is correct
22 Correct 43 ms 7196 KB Output is correct
23 Correct 44 ms 7768 KB Output is correct
24 Correct 128 ms 17584 KB Output is correct
25 Correct 122 ms 16036 KB Output is correct
26 Correct 94 ms 13500 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 42 ms 8276 KB Output is correct
30 Correct 40 ms 7404 KB Output is correct
31 Correct 41 ms 8272 KB Output is correct
32 Correct 39 ms 7504 KB Output is correct
33 Correct 40 ms 6996 KB Output is correct
34 Correct 43 ms 7804 KB Output is correct
35 Correct 42 ms 8280 KB Output is correct
36 Correct 194 ms 21480 KB Output is correct
37 Correct 178 ms 21424 KB Output is correct
38 Correct 176 ms 20920 KB Output is correct
39 Correct 126 ms 17604 KB Output is correct
40 Correct 184 ms 20900 KB Output is correct
41 Correct 223 ms 25948 KB Output is correct
42 Correct 217 ms 26804 KB Output is correct
43 Correct 239 ms 29356 KB Output is correct
44 Correct 237 ms 30788 KB Output is correct
45 Correct 200 ms 21172 KB Output is correct
46 Correct 243 ms 19628 KB Output is correct
47 Correct 227 ms 19884 KB Output is correct
48 Correct 172 ms 20920 KB Output is correct