oj.uz

Submission #893324

# Submission time Handle Problem Language Result Execution time Memory
893324 2023-12-27T02:02:15 Z vjudge1 Inspections (NOI23_inspections) C++17
0 / 100
 133 ms 9040 KB 
#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{
int u,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){
    //divide to (*it).l a[i].fi-1 a[i].fi,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
    //cerr<<i<<" "<<vcl.l<<" "<<vcl.r<<'\n';
    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){
    long long dis=(xx-v.time-1);
    //cout<<i<<" "<<v.l<<" "<<v.r<<" "<<v.time<<'\n';
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 40 ms 7080 KB Output is correct
4 Correct 43 ms 7188 KB Output is correct
5 Correct 133 ms 8460 KB Output is correct
6 Incorrect 79 ms 9040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -