Submission #1203816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203816		agrim_09	Inspections (NOI23_inspections)	C++20	0 / 100	1431 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;


// #ifndef ONLINE_JUDGE
// #include "algo/Standard_Stuff/debug.cpp"
// #else
// #define debug(...) 42
// #endif

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; //judge();
    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);
            else
                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;
            }
        }
    }
    sort(deltas.begin(),deltas.end());
    //debug(deltas);
    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==deltas.size()){
            cout << 0 << ' ';
            continue;
        }
        if(idx==0){
            cout << psum.back() << ' ';
        }
        else{
            cout << psum.back() - psum[idx-1] << ' ';
        }

    }
}

Compilation message (stderr)

Main.cpp: In function 'void judge()':
Main.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen("1.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     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