oj.uz

Submission #1019475

# Submission time Handle Problem Language Result Execution time Memory
1019475 2024-07-10T22:55:09 Z vjudge1 Sails (IOI07_sails) C++17
100 / 100
 146 ms 8164 KB 
#include<bits/stdc++.h>
using namespace std;
struct segtree{
    struct node{
        long long sum,mn,lz;
        node(){mn=sum=lz=0;}
    } T[1<<18];
    void pd(int i,int sz){
        T[i].mn+=T[i].lz;
        T[i].sum+=sz*T[i].lz;
        if(sz>1)T[i*2].lz+=T[i].lz,
            T[i*2+1].lz+=T[i].lz;
        T[i].lz=0;
    }
    int walk(int i,int l,int r,int p){
        if(l==r)return l;
        pd(i*2,r-l+2>>1),pd(i*2+1,r-l+1>>1);
        if(p>=T[i*2].mn)
            return walk(i*2,l,l+r>>1,p);
        return walk(i*2+1,l+r+2>>1,r,p);
    }
    int atpos(int i,int l,int r,int p){
        pd(i,r-l+1);if(l==r)return T[i].mn;
        if(l+r>>1<p)
            return atpos(i*2+1,l+r+2>>1,r,p);
        else return atpos(i*2,l,l+r>>1,p);
    }
    long long query(int i,int l,int r,int ll,int rr){
        pd(i,r-l+1);
        if(ll>r||l>rr) return 0;
        if(ll<=l&&r<=rr)
            return T[i].lz++,pd(i,r-l+1),T[i].sum;
        long long ans=query(i*2,l,l+r>>1,ll,rr)+
            query(i*2+1,l+r+2>>1,r,ll,rr);
        T[i].mn=min(T[i*2].mn,T[i*2+1].mn);
        T[i].sum=T[i*2].sum+T[i*2+1].sum;
        return ans;
    }
    segtree(){T[1].lz=-1;}
} ST;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    long long ans=0;
    cin>>n;
    vector<pair<int,int>>masts(n);
    for(auto&[h,k]:masts)
        cin>>h>>k;
    sort(masts.begin(),masts.end());
    for(auto[h,k]:masts){
        int y=ST.atpos(1,1,1e5+1,h-k+1);
        int posl=ST.walk(1,1,1e5+1,y-1);
        int posr=ST.walk(1,1,1e5+1,y);
        ans+=ST.query(1,1,1e5+1,posl,h);
        k-=max(0,h-posl+1);
        ans+=ST.query(1,1,1e5+1,posr,posr+k-1);
    }
    cout<<ans<<'\n';
}

Compilation message

sails.cpp: In member function 'int segtree::walk(int, int, int, int)':
sails.cpp:17:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         pd(i*2,r-l+2>>1),pd(i*2+1,r-l+1>>1);
      |                ~~~^~
sails.cpp:17:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         pd(i*2,r-l+2>>1),pd(i*2+1,r-l+1>>1);
      |                                   ~~~^~
sails.cpp:19:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |             return walk(i*2,l,l+r>>1,p);
      |                               ~^~
sails.cpp:20:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         return walk(i*2+1,l+r+2>>1,r,p);
      |                           ~~~^~
sails.cpp: In member function 'int segtree::atpos(int, int, int, int)':
sails.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         if(l+r>>1<p)
      |            ~^~
sails.cpp:25:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |             return atpos(i*2+1,l+r+2>>1,r,p);
      |                                ~~~^~
sails.cpp:26:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         else return atpos(i*2,l,l+r>>1,p);
      |                                 ~^~
sails.cpp: In member function 'long long int segtree::query(int, int, int, int, int)':
sails.cpp:33:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         long long ans=query(i*2,l,l+r>>1,ll,rr)+
      |                                   ~^~
sails.cpp:34:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |             query(i*2+1,l+r+2>>1,r,ll,rr);
      |                         ~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6744 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6492 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6744 KB Output is correct
2 Correct 33 ms 7004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7516 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7772 KB Output is correct
2 Correct 98 ms 8024 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8024 KB Output is correct
2 Correct 67 ms 8024 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 8164 KB Output is correct
2 Correct 98 ms 8028 KB Output is correct