Submission #862174

#	Time	Username	Problem	Language	Result	Execution time	Memory
862174		prohacker	Inspections (NOI23_inspections)	C++14	100 / 100	344 ms	33808 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define FOR(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define FORE(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define par pair<int , int>
#define ll long long
#define int long long

using namespace std;

const int N = 2e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;

int n,sum[N],m,Q;
pair<int,int> q[N],a[N];
set<pair<int,int>> s;
int ans[N],kq[N];
vector<pair<int,int>> pos;

int get_sum(int l, int r) {
    return sum[r] - sum[l-1];
}

int Find(int x) {
    int l = 1;
    int r = Q;
    int res = r+1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(q[mid].first >= x) {
            res = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    return res;
}

void update(int i, int val) {
    if(i == 0) {
        return;
    }
    kq[0] += val;
    kq[i+1] -= val;
}

main()
{
    if (fopen("inspections.inp", "r")) {
        freopen("inspections.inp", "r", stdin);
        freopen("inspections.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> Q;
    for(int i = 1 ; i <= m ; i++) {
        cin >> a[i].first >> a[i].second;
        sum[i] = sum[i-1] + (a[i].second-a[i].first+1);
    }
    for(int i = 1 ; i <= Q ; i++) {
        cin >> q[i].first;
        q[i].second = i;
    }
    sort(q+1,q+Q+1);
    s.insert({0,0});
    s.insert({n+1,0});
    for(int i = 1 ; i <= m ; i++) {
        int l = a[i].first;
        int r = a[i].second;
        int L = l;
        auto u = s.upper_bound({l,INF});
        u--;
        auto v = s.upper_bound({r,INF});
        if(v == s.end()) {
            v--;
        }
        pos.clear();
        for(auto it = u ; it != v ; it++) {
            int id = ((*it).second);
            pos.push_back({(*it).first,(*it).second});
            auto hihi = it;
            hihi++;
            if(id != 0) {
                int val = get_sum(id,i-1)-(l-a[id].first)+(l-L);
                int x = Find(val);
                int R = min(r,((*hihi).first-1));
                update(x-1,R-l+1);
            }
            l = ((*hihi).first);
        }
        pos.push_back({(*v).first,(*v).second});
        int len = pos.size()-1;
        for(int p = 1 ; p < len ; p++) {
            s.erase({pos[p].first,pos[p].second});
        }
        s.erase(u);
        if(r+1 < pos[len].first) {
            s.insert({r+1,pos[len-1].second});
        }
        if(pos[0].first < L) {
            s.insert({pos[0].first,pos[0].second});
        }
        s.insert({L,i});
    }
    for(int i = 1 ; i <= Q ; i++) {
        kq[i] += kq[i-1];
        ans[q[i].second] = kq[i];
    }
    for(int i = 1 ; i <= Q ; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int Find(long long int)':
Main.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: At global scope:
Main.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("inspections.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("inspections.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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