oj.uz

Submission #599610

# Submission time Handle Problem Language Result Execution time Memory
599610 2022-07-19T16:39:02 Z gg123_pe Sails (IOI07_sails) C++14
100 / 100
 745 ms 6740 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4300 KB Output is correct
2 Correct 17 ms 4424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4364 KB Output is correct
2 Correct 17 ms 4348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4336 KB Output is correct
2 Correct 18 ms 4408 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4312 KB Output is correct
2 Correct 19 ms 4368 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4328 KB Output is correct
2 Correct 27 ms 4308 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4584 KB Output is correct
2 Correct 171 ms 5016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5040 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 5392 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 5956 KB Output is correct
2 Correct 572 ms 6020 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 6308 KB Output is correct
2 Correct 379 ms 5984 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 6740 KB Output is correct
2 Correct 583 ms 6292 KB Output is correct