oj.uz

Submission #586755

# Submission time Handle Problem Language Result Execution time Memory
586755 2022-06-30T16:25:40 Z Bench0310 Sails (IOI07_sails) C++17
100 / 100
 205 ms 6960 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=100000;
vector<int> mn(4*(N+5),0);
vector<int> mx(4*(N+5),0);
vector<int> lazy(4*(N+5),0);

void pull(int idx)
{
    mn[idx]=min(mn[2*idx],mn[2*idx+1]);
    mx[idx]=max(mx[2*idx],mx[2*idx+1]);
}

void apply(int idx,int x)
{
    mn[idx]+=x;
    mx[idx]+=x;
    lazy[idx]+=x;
}

void push(int idx)
{
    for(int i=0;i<2;i++) apply(2*idx+i,lazy[idx]);
    lazy[idx]=0;
}

void update(int idx,int l,int r,int ql,int qr,int x)
{
    if(ql>qr) return;
    if(l==ql&&r==qr) apply(idx,x);
    else
    {
        int m=(l+r)/2;
        push(idx);
        update(2*idx,l,m,ql,min(qr,m),x);
        update(2*idx+1,m+1,r,max(ql,m+1),qr,x);
        pull(idx);
    }
}

int query(int idx,int l,int r,int pos)
{
    if(l==r) return mn[idx];
    int m=(l+r)/2;
    push(idx);
    if(pos<=m) return query(2*idx,l,m,pos);
    else return query(2*idx+1,m+1,r,pos);
}

int descend(int idx,int l,int r,int ql,int qr,int val,int dir)
{
    if(ql>qr) return -1;
    if(!(mn[idx]<=val&&val<=mx[idx])) return -1;
    if(l==r) return l;
    int m=(l+r)/2;
    push(idx);
    if(dir==0)
    {
        int t=descend(2*idx,l,m,ql,min(qr,m),val,dir);
        if(t!=-1) return t;
        return descend(2*idx+1,m+1,r,max(ql,m+1),qr,val,dir);
    }
    else
    {
        int t=descend(2*idx+1,m+1,r,max(ql,m+1),qr,val,dir);
        if(t!=-1) return t;
        return descend(2*idx,l,m,ql,min(qr,m),val,dir);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<array<int,2>> v(n+1,{0,0});
    for(int i=1;i<=n;i++)
    {
        auto &[h,k]=v[i];
        cin >> h >> k;
    }
    sort(v.begin(),v.end());
    int p=N+1;
    for(int i=1;i<=n;i++)
    {
        auto [h,k]=v[i];
        p-=(h-v[i-1][0]);
        int a=query(1,1,N,p+k-1);
        int l=descend(1,1,N,p,N,a,0);
        int r=descend(1,1,N,p,N,a,1);
        int cnt=(p+k-1-l+1);
        update(1,1,N,p,l-1,1);
        update(1,1,N,r-cnt+1,r,1);
    }
    ll res=0;
    for(int i=1;i<=N;i++)
    {
        ll c=query(1,1,N,i);
        res+=((c-1)*c/2);
    }
    cout << res << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5028 KB Output is correct
2 Correct 10 ms 4948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4948 KB Output is correct
2 Correct 10 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5028 KB Output is correct
2 Correct 10 ms 5032 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4948 KB Output is correct
2 Correct 17 ms 5092 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4948 KB Output is correct
2 Correct 12 ms 5052 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5076 KB Output is correct
2 Correct 60 ms 5556 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 5928 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 6380 KB Output is correct
2 Correct 131 ms 6520 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 6756 KB Output is correct
2 Correct 100 ms 6356 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 6960 KB Output is correct
2 Correct 147 ms 6868 KB Output is correct