Submission #1290853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290853		uocgi	Inspections (NOI23_inspections)	C++20	77 / 100	1741 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define int long long
#define TASK "Inspections"
const int maxn = 3e5+5;
const int mod = 1e9+7;
int m,n,q;
ii a[maxn];
namespace sub1{
    vector<int> b;
    int pos[maxn];
    int calc(int x){
        int cnt = 0;
        for (int i = 1;i<=n;i++) pos[i] = -1;
        for (int i = (int)b.size()-1;i>=0;i--){
//            cout << i << " " << pos[b[i]] << "\n";
            if (pos[b[i]]!=-1){
                if (pos[b[i]]-i-1>=x) cnt++;
            }
            pos[b[i]] = i;
        }
        return cnt;
    }
    void solve(){
        for (int i = 1;i<=m;i++){
            for (int j = a[i].fi;j<=a[i].se;j++){
                b.pb(j);
            }
        }
//        for (int x : b) cout << x << " ";
//        cout << "\n";
        while (q--){
            int x; cin >> x;
            cout << calc(x) << " ";
        }
    }
}
namespace sub2{
    vector<int> b;
    int pos[maxn];
    int calc(int x){
        int cnt = 0;
        for (int i = 1;i<=n;i++) pos[i] = -1;
        for (int i = (int)b.size()-1;i>=0;i--){
//            cout << i << " " << pos[b[i]] << "\n";
            if (pos[b[i]]!=-1){
                if (pos[b[i]]-i-1>=x) cnt++;
            }
            pos[b[i]] = i;
        }
        return cnt;
    }
    vector<int> diff;
    void prepare(){
        for (int i = 1;i<=n;i++) pos[i] = -1;
        for (int i = (int)b.size()-1;i>=0;i--){
//            cout << i << " " << pos[b[i]] << "\n";
            if (pos[b[i]]!=-1){
                diff.pb(pos[b[i]]-i-1);
            }
            pos[b[i]] = i;
        }
        sort(diff.begin(),diff.end());
    }
    void solve(){
        for (int i = 1;i<=m;i++){
            for (int j = a[i].fi;j<=a[i].se;j++){
                b.pb(j);
            }
        }
//        for (int x : b) cout << x << " ";
        prepare();
        while (q--){
            int x; cin >> x;
            int lb = lower_bound(diff.begin(),diff.end(),x)-diff.begin();
            cout << diff.size()-lb << " ";
        }
    }
}
namespace sub3{
    map<int,int> mp;
    bool check(){
        for (int i = 1;i<=m;i++) if (a[i].fi!=1) return 0;
        return 1;
    }
    int pre[maxn];
    void solve(){
        stack<int> st;
        for (int i = 1;i<=m;i++){
            pre[i] = pre[i-1]+a[i].se;
        }
        for (int i = m;i>=1;i--){
            int cur = i;
            while (st.size() && a[st.top()].se<=a[i].se){
                if (cur == i) mp[a[i].se-1]+= a[st.top()].se;
                else {
//                    cout << i << " " << st.top() << " " << cur << "\n";
//                    cout << i << ' ' << st.top() << " " << a[i].se-1+pre[st.top()-1]-pre[cur] <<  "\n";
                    mp[a[i].se-1+pre[st.top()-1]-pre[i]]+=a[st.top()].se-a[cur].se;
                }
                cur = st.top();
                st.pop();
            }
            if (st.size()){
//                cout << i << " " << st.top() << "\n";
                if (cur == i){
                    mp[a[i].se-1]+=a[i].se;
                }
                else {
                    mp[a[i].se-1+pre[st.top()-1]-pre[i]]+=a[i].se-a[cur].se;
                }
            }
            st.push(i);
        }
        vector<int> val,tt;
        int tmpp = 0;
        for (ii x : mp){
            tmpp+= x.se;
            val.pb(tmpp);
            tt.pb(x.fi);
//            cout << x.fi << " " << x.se << "\n";
        }
        for (int i = 1;i<=q;i++){
            int x; cin >> x;
            int ub = lower_bound(tt.begin(),tt.end(),x)-tt.begin();
            if (ub == tt.size()){
                cout << 0 << " ";
            }
            else {
                if (!ub) cout << tmpp << " ";
                else cout << tmpp-val[ub-1] << " ";
            }
        }
    }
}
namespace sub4{
    struct segtree{
        int st[maxn*4],lz[maxn*4];
        void init(){
            for (int i = 1;i<=n*4;i++) lz[i] = -1;
        }
        void push(int id, int l, int r){
            if (lz[id]!=-1 && l!=r){
                int m = l+r>>1;
                st[id*2] = (m-l+1)*lz[id];
                st[id*2+1] = (r-m)*lz[id];
                lz[id*2] = lz[id];
                lz[id*2+1] = lz[id];
                lz[id] = -1;
            }
        }
        void up(int id, int l, int r, int u, int v, int val){
            if (u>r || l>v) return;
            push(id,l,r);
            if (l>=u &&r<=v) {
                st[id]=(r-l+1)*val;
                lz[id]=val;
                push(id,l,r);
                return;
            }
            int m= l+r>>1;
            up(id*2,l,m,u,v,val);
            up(id*2+1,m+1,r,u,v,val);
            st[id] = st[id*2]+st[id*2+1];
        }
        int get(int id, int l, int r, int u, int v){
            if (u>r || l>v) return 0;
            push(id,l,r);
            if (l>=u && r<=v) return st[id];
            int m = l+r>>1;
            return get(id*2,l,m,u,v)+get(id*2+1,m+1,r,u,v);
        }
    } it;
    unordered_map<int,int> mp;
    int pre[maxn];
    void solve(){
        it.init();
        for (int i = 1;i<=m;i++){
            pre[i]+= pre[i-1]+a[i].se-a[i].fi+1;
        }
        for (int i = 1;i<=m;i++){
            it.up(1,1,n,1,n,0);
            it.up(1,1,n,a[i].fi,a[i].se,1);
            int cur = a[i].se-a[i].fi+1;
            for (int j = i+1;j<=m;j++){
                if (cur== 0) break;
                if (a[i].se-a[j].fi+pre[j-1]-pre[i]<0) continue;
//                cout << a[i].se-a[j].fi+1+pre[j-1]-pre[i]  << " " << i <<  " " << j<< "\n";
                int sum = it.get(1,1,n,a[j].fi,a[j].se);
                mp[a[i].se-a[j].fi+pre[j-1]-pre[i]]+= sum;
                cur-=sum;
                it.up(1,1,n,a[j].fi,a[j].se,0);
            }
        }
//        cout << pre[2]-pre[1] << "\n";
//        cout << it.get(1,1,n,1,n);
//        for (ii x : mp){
//            cout << x.fi << " " << x.se << "\n";
//        }
        vector<int> val,tt;
        vector<ii> b;
        int tmpp = 0;
        for (ii x : mp){
            b.pb(x);
//            tmpp+= x.se;
//            val.pb(tmpp);
//            tt.pb(x.fi);
//            cout << x.fi << " " << x.se << "\n";
        }
        sort(b.begin(),b.end());
        for (ii x : b){
            tmpp+=x.se;
            val.pb(tmpp);
            tt.pb(x.fi);
        }
        for (int i = 1;i<=q;i++){
            int x; cin >> x;
            int ub = lower_bound(tt.begin(),tt.end(),x)-tt.begin();
            if (ub == tt.size()){
                cout << 0 << " ";
            }
            else {
                if (!ub) cout << tmpp << " ";
                else cout << tmpp-val[ub-1] << " ";
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    if (fopen(TASK".inp","r")){
        freopen(TASK".inp","r",stdin);
        freopen(TASK".out","w",stdout);
    }
    cin >> n >> m >> q;
    for (int i = 1;i<=m;i++) cin >> a[i].fi >> a[i].se;
//    sub1::solve();
//    sub2::solve();
//    sub4::solve();
    if (sub3::check()) sub3::solve();
    else if (m<=2000) sub4::solve();
    else sub2::solve();
//    sub3::solve();
}

Compilation message (stderr)

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

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