Submission #1203817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203817		agrim_09	Inspections (NOI23_inspections)	C++20	0 / 100	1555 ms	1114112 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;


void judge(){
    srand(time(NULL));
    #ifndef ONLINE_JUDGE
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    #endif
}

struct tuplet{
    int l,r,t;
};

// Look for edge cases!!!
signed main(){
    fastio; 
    int n,m,q; cin >> n >> m >> q;
    vector<pair<int,int>>a(m);
    for(auto &[x,y]:a){
        cin >> x >> y; x--; y--;
    }
    vector<tuplet>ranges;
    set<int> tmp = {n - 1};
    for (int i = 0; i < m; i++){
        if (a[i].first != 0)
            tmp.insert(a[i].first - 1);
        tmp.insert(a[i].second);
    }
    int prev = 0;
    for (auto x : tmp){
        ranges.pb({prev, x, inf});
        prev = x + 1;
    }

    vector<pair<int,int>>deltas;
    int curr_time = 0;
    for(int i = 0;i<m;i++){
        for(int j = 0;j<(int)(ranges.size());j++){
            if(a[i].first<=ranges[j].l and ranges[j].r<=a[i].second){
                if(ranges[j].t==inf){
                    ranges[j].t = curr_time;
                }
                else{
                    deltas.pb({curr_time-ranges[j].t,ranges[j].r-ranges[j].l+1});
                }
                ranges[j].t = curr_time;
                curr_time += ranges[j].r - ranges[j].l + 1;
            }
            else if(a[i].second<ranges[j].l or a[i].first>ranges[j].r){
                continue;
            }
            else{
                assert(false);
                return 0;
            }
        }
    }
    sort(deltas.begin(),deltas.end());
    vector<int>psum(deltas.size());
    int curr = 0;
    for(int i = 0;i<deltas.size();i++){
        curr += deltas[i].second;
        psum[i] = curr;
    }

    while(q--){
        int v; cin >> v;
        auto it = lower_bound(deltas.begin(),deltas.end(),make_pair(v,inf));
        int idx = it - deltas.begin();
        if(idx==0){
            cout << psum.back() << ' ';
        }
        else{
            cout << psum.back() - psum[idx-1] << ' ';
        }

    }
}

Compilation message (stderr)

Main.cpp: In function 'void judge()':
Main.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen("1.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("2.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 23