oj.uz

Submission #833015

# Submission time Handle Problem Language Result Execution time Memory
833015 2023-08-21T19:24:12 Z Liudas Inspections (NOI23_inspections) C++17
22 / 100
 577 ms 30732 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
struct seg{
    int l;
    int r;
    int time;
    bool operator<(const seg &a)const{
        return l < a.l;
    }
};
// need : inter left 
// got : cover all inter right

map<int, int> vals;
set<seg> in;
vector<seg> to_err, to_add;
void compare(seg &a, seg &b){
    if(b.l < a.l){
        seg c = {b.l, a.l-1, b.time};
        to_add.push_back(c);
        b.time += a.l - b.l;
        b.l = a.l;
    }
    if(b.r > a.r){
        seg c = {a.r + 1, b.r, b.time + a.r - b.l + 1};
        to_add.push_back(c);
        b.r = a.r;
    }
}
signed main(){
    int N, Q, M;
    cin >> N >> M >> Q;
    vector<seg> arr(M);
    int day = 0;
    for(int i = 0; i < M; i ++){
        int a, b;
        cin >> a >> b;
        arr[i] = {a,b,day};
        day += b-a+1;
    }
    for(int i = 0; i < M; i ++){
        seg a = arr[i];
        auto p = in.begin();
        while(p != in.end() && (*p).l <= a.r){
            seg b = *p;
            to_err.push_back(b);
            //cout << " A   " << a.l << " " << a.r << " " << a.time << endl;
            //cout << " B   " << b.l << " " << b.r << " " << b.time << endl;
            compare(a, b);
            //cout << "AD A   " << a.l << " " << a.r << " " << a.time << endl;
            //cout << "AD B   " << b.l << " " << b.r << " " << b.time << endl;
            int lmax = max(a.l, b.l);
            int rmin = min(a.r, b.r);
            int td = b.l - a.l;
            vals[a.time + td - b.time - 1] += rmin-lmax+1;
            p++;
        }
        for(auto j : to_err){
            in.erase(j);
        }
        to_err.clear();
        for(auto j : to_add){
            in.insert(j);
        }
        to_add.clear();
        in.insert(a);
    }
    for(auto i : in){
        //cout << "liko " << i.l << " " << i.r << " " << i.time << endl;
    }
    vector<pair<int, int>> pref;
    for(auto[l, r] : vals){
        pref.push_back({l, r});
        //cout << l <<" " << r << endl;
    }
    pref.push_back({(int)1e16, 0ll});
    for(int i = (int)pref.size()-2; i > -1; i --){
        pref[i].second += pref[i+1].second;
    }
    for(auto[l, r] : pref){
       //cout << "P   " << l << " " << r << endl;
    }
    for(int i = 0; i < Q; i ++){
        int q;
        cin >> q;
        cout << (*lower_bound(pref.begin(), pref.end(), make_pair(q, 0ll))).second << " ";
    }
    cout << endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:73:14: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   73 |     for(auto i : in){
      |              ^
Main.cpp:85:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   85 |     for(auto[l, r] : pref){
      |             ^~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 261 ms 1064 KB Output is correct
4 Correct 268 ms 1348 KB Output is correct
5 Correct 577 ms 30700 KB Output is correct
6 Correct 569 ms 30732 KB Output is correct
7 Correct 460 ms 20868 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -