oj.uz

Submission #1106342

# Submission time Handle Problem Language Result Execution time Memory
1106342 2024-10-30T03:13:30 Z ro9669 Inspections (NOI23_inspections) C++17
22 / 100
 211 ms 23764 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;
const ll inf = ll(1e18)+7;

int n , m , q;
set<pair<ii , ll>> st;
vector<pair<ll , int>> event;
ll query[maxN] , res[maxN];
int id[maxN];

void solve(){
    cin >> n >> m >> q;
    ll t = 0;
    for (int i = 1 ; i <= m ; i++){
        int l , r;
        cin >> l >> r;
        while (true){
            auto it = st.lower_bound({{l , r} , t});
            if (it == st.end()) break;
            int cur_l = it->fi.fi;
            int cur_r = it->fi.se;
            ll cur_t = it->se;
            if (cur_r > r) break;
            event.push_back({t + 1ll * (cur_l - l) - cur_t , cur_r - cur_l + 1});
            st.erase(it);
        }
        set<pair<ii , ll>>::iterator it;
        st.insert({{l , r} , t});
        it = st.find({{l , r} , t});
        if (it != st.begin()){
            int cur_l = prev(it)->fi.fi;
            int cur_r = prev(it)->fi.se;
            ll cur_t = prev(it)->se;
            if (l <= cur_r && cur_r <= r){
                st.erase(prev(it));
                event.push_back({t - cur_t - 1ll * (l - cur_l) , cur_r - l + 1});
                st.insert({{cur_l , l - 1} , cur_t});
            }
        }
        it = st.find({{l , r} , t});
        if (next(it) != st.end()){
            int cur_l = next(it)->fi.fi;
            int cur_r = next(it)->fi.se;
            ll cur_t = next(it)->se;
            if (cur_l <= r && r <= cur_r){
                st.erase(next(it));
                event.push_back({t + 1ll * (cur_l - l) - cur_t , r - cur_l + 1});
                st.insert({{r + 1 , cur_r} , cur_t + 1ll * (r + 1 - cur_l)});
            }
        }
        it = st.find({{l , r} , t});
        if (it != st.begin()){
            int cur_l = prev(it)->fi.fi;
            int cur_r = prev(it)->fi.se;
            ll cur_t = prev(it)->se;
            if (cur_l < l && r < cur_r){
                st.erase(prev(it));
                st.insert({{cur_l , l - 1} , cur_t});
                st.insert({{r + 1 , cur_r} , cur_t + 1ll * (r + 1 - cur_l)});
                event.push_back({t - cur_t - 1ll * (cur_l - l) , r - l + 1});
            }
        }
        t += 1ll * (r - l + 1);
    }
    for (int i = 1 ; i <= q ; i++){
        cin >> query[i];
        id[i] = i;
    }
    sort(id + 1 , id + q + 1 , [](int x , int y){
         return query[x] > query[y];
    });
    sort(all(event)); reverse(all(event));
    ll sum = 0;
    for (int i = 1 , j = -1 ; i <= q ; i++){
        while (j + 1 < sz(event) && event[j + 1].fi > query[id[i]]){
            j++;
            sum += 1ll * event[j].se;
        }
        res[id[i]] = sum;
    }
    for (int i = 1 ; i <= q ; i++) cout << res[i] << " ";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 45 ms 6264 KB Output is correct
4 Correct 44 ms 7000 KB Output is correct
5 Correct 211 ms 23764 KB Output is correct
6 Correct 211 ms 23084 KB Output is correct
7 Correct 148 ms 16948 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 23.0

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