Submission #599610

#	Time	Username	Problem	Language	Result	Execution time	Memory
599610		gg123_pe	Sails (IOI07_sails)	C++14	100 / 100	745 ms	6740 KiB

sails

#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef pair <pair<char,char>, pair<char,char>> T; 
#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 1e5 + 5; 

int n; 
vector <pair<int,int>> v; 
ll st[4*N], lazy[4*N]; 

void go(int id, int l, int r){
    int m = (l+r)>>1; 
    st[id<<1] += (ll) (m-l+1) * lazy[id]; 
    st[id<<1|1] += (ll) (r-m) * lazy[id]; 
    lazy[id<<1] += lazy[id], lazy[id<<1|1] += lazy[id];  
    lazy[id] = 0; 
}
void upd(int id, int l, int r, int x, int y, ll val){
    if(r < x or y < l) return; 
    if(x <= l and r <= y){
        lazy[id] += val; 
        st[id] += (ll) (r - l + 1) * val; 
        return; 
    }
    go(id, l, r); 
    int m = (l+r)>>1; 
    upd(id<<1, l, m, x, y, val), upd(id<<1|1, m+1, r, x, y, val); 
    st[id] = st[id<<1] + st[id<<1|1]; 
}

ll query(int id, int l, int r, int x, int y){
    if(r < x or y < l) return 0; 
    if(x <= l and r <= y) return st[id]; 
    go(id, l, r); 
    int m = (l+r)>>1; 
    return query(id<<1, l, m, x, y) + query(id<<1|1, m+1, r, x, y); 
}

ll get(int pos){
    return query(1, 1, N-1, pos, pos); 
}
int main(){
    cin >> n; 

    f(i,0,n){
        int h, w; 
        cin >> h >> w; 

        v.push_back({h, w}); 
    }

    sort(v.begin(), v.end()); 

    for(auto p: v){
        int h = p.first, w = p.second; 

        upd(1, 1, N-1, h-w+1, h, 1); 

        ll pos = h-w+1, val = get(pos);

        if(pos > 1){
            ll v1 = get(pos-1); 
            if(v1 >= val) continue; 

            int L, R; 
            int l = 1, r = pos-1; 
            while(l < r){
                int m = (l+r)>>1; 
                if(get(m) != v1) l = m+1; 
                else r = m; 
            }

            L = l; 
            l = pos, r = h; 
            while(l < r){
                int m = (l+r+1)>>1; 
                if(get(m) != val) r = m-1; 
                else l = m; 
            }
            R = l; 

            int x = pos-L, y = R-pos+1; 
            x = min(x, y); 

            upd(1, 1, N-1, L, L+x-1, 1); 
            upd(1, 1, N-1, R-x+1, R, -1);
        }   
    }
    ll ans = 0; 
    f(i,1,N){
        ll w = get(i); 
        ans += (w * (w-1)) / 2;
    }

    cout << ans << "\n"; 
    return 0; 
}

• 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