Submission #1019477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019477		boyliguanhan	Sails (IOI07_sails)	C++17	100 / 100	135 ms	8540 KiB

sails

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10