Submission #893332

#	Time	Username	Problem	Language	Result	Execution time	Memory
893332		karrigan	Inspections (NOI23_inspections)	C++14	100 / 100	268 ms	26688 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
#define pil pair<int,long long>
const int maxn=2e5+9;
struct line{
int l,r;
long long time;
bool operator < (const line &p)const {
if (l==p.l)return r<p.r;
return l<p.l;
}
};
struct suzy{
long long u;
int id;
bool operator < (const suzy &p)const {
return u<p.u;
}
}b[maxn];
long long pf[maxn];
pii a[maxn];
long long sum[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m,q;
    cin>>n>>m>>q;
    for1(i,1,m)cin>>a[i].fi>>a[i].se;
    for1(i,1,q){
    b[i].id=i;
    cin>>b[i].u;
    }
    sort(b+1,b+1+q);
    multiset<line>t;
    t.insert({1,n,-1});
    long long ss=0;
    for1(i,1,m){
    line dm={a[i].fi,-1,-1};
    vector<line>tmp;
    while (!t.empty()){
    auto it=t.lower_bound(dm);
    if (it==t.end())break;
    if ((*it).l>a[i].se)break;
    auto vcl=(*it);
    if ((*it).r>a[i].se){
    t.erase(it);
    t.insert({a[i].se+1,vcl.r,vcl.time+(vcl.time!=-1)*(a[i].se-vcl.l+1)});
    tmp.pb({vcl.l,a[i].se,vcl.time});
    }
    else {
    t.erase(it);
    tmp.pb(vcl);
    }
    }
    auto it=t.lower_bound(dm);
    if (!t.empty()&&it!=t.begin()){
    it--;
    auto vcl=(*it);
    if (vcl.r>=a[i].fi){
    if (vcl.r>a[i].se){
    t.erase(it);
    t.insert({vcl.l,a[i].fi-1,vcl.time});
    t.insert({a[i].se+1,vcl.r,vcl.time+(vcl.time!=-1)*(a[i].se-vcl.l+1)});
    tmp.pb({a[i].fi,a[i].se,vcl.time+(vcl.time!=-1)*(a[i].fi-1-vcl.l+1)});
    }
    else {
    //divide to (*it).l a[i].fi-1 a[i].fi (*it).r
    t.erase(it);
    t.insert({vcl.l,a[i].fi-1,vcl.time});
    tmp.pb({a[i].fi,vcl.r,vcl.time+(vcl.time!=-1)*(a[i].fi-1-vcl.l+1)});
    }
    }
    }
    t.insert({a[i].fi,a[i].se,ss});
    long long xx=ss;
    sort(all(tmp));
    for (auto v:tmp){
    //v.time+2 to xx
    long long dis=(xx-(v.time+2)+1);
    int l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid].u<=dis){
    ans=mid;
    l=mid+1;
    }
    else r=mid-1;
    }
    if (v.time==-1)ans=-1;
    if (ans!=-1){
    pf[1]+=(v.r-v.l+1);
    pf[ans+1]-=(v.r-v.l+1);
    }
    xx+=(v.r-v.l+1);
    }
    ss+=(a[i].se-a[i].fi+1);
    }
    //for (auto v:t)cout<<v.l<<" "<<v.r<<" "<<v.time<<'\n';
    for1(i,1,q)pf[i]+=pf[i-1];
    for1(i,1,q)sum[b[i].id]=pf[i];
    for1(i,1,q)cout<<sum[i]<<" ";
}

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