Submission #1234045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234045		dcz0711	Sails (IOI07_sails)	C++20	100 / 100	90 ms	4796 KiB

sails

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define uint unsigned int
#define inf (ll)1e18
#define e1 ' '
#define e2 '\n'
#define ld long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sf(x) sizeof(x)
#define print_double(d, n) cout<<fixed<<setprecision(n)<<d<<end1;

bool dcmp(int x, int y) {return x > y;}
bool acmp(int x, int y) {return x < y;}
bool afcmp(pair<int, int> a, pair<int, int> b) {return a.first < b.first;}
bool dfcmp(pair<int, int> a, pair<int, int> b) {return a.first > b.first;}
bool ascmp(pair<int, int> a, pair<int, int> b) {return a.second < b.second;}
bool dscmp(pair<int, int> a, pair<int, int> b) {return a.second > b.second;}
int aabs(int a) {return a < 0 ? -a : a;}
ll tmax(ll a, ll b, ll c) {return max(max(a, b), c);}
ll tmin(ll a, ll b, ll c) {return min(min(a, b), c);}
bool in_range(int x, int l, int r) {return x >= l && x <= r;}

bool is_prime(int val) {
    if (val == 2) {
        return true;
    }
    if (val % 2 == 0) {
        return false;
    }
    for (int i = 3; i * i <= val; i += 2) {
        if (val % i == 0) {
            return false;
        }
    }
    return true;
}

int lowbit(int x) {return x & (-x);}
inline ll gcd(ll x, ll y) {return y ? gcd(y, x % y) : x;}
inline ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

const int maxN = 1e5+5;
const int maxH = 1e5+5;
vector<pair<ll,ll>> s;
ll diff[maxH];
pair<int, int> d[3*maxH]; // (first nonzero )
int H, curH;

pii merge(pii l, pii r){
    int lz = l.first == -1?r.first:l.first;
    int rz = r.second==-1?l.second:r.second;
    return mp(lz, rz);
}
void build(int l, int r, int p) {
    if (l == r) { // leaf node
        d[p] = mp(-1, -1);        
        return;
    }
    int m = l + ((r - l)/2);
    build(l, m, 2*p);
    build(m + 1, r, 2*p+1);
    d[p] = merge(d[2*p],d[2*p+1]);
}
void _update(int idx, bool flag, int l, int r, int p) {
    if (l == r) { // the one leaf node we need to update 
        if(flag){ // zero
            d[p] = mp(-1, -1);
        }
        else{ // nonzero
            d[p] = mp(idx,idx);
        }
        return;
    }
    int m = l + ((r - l) / 2);
    if (idx <= m) {
        _update(idx, flag, l, m, 2*p);
    }
    else {
        _update(idx, flag,  m + 1, r, 2*p+1);
    }
    d[p] = merge(d[2* p], d[2*p+1]); 
}
int _query_left(int p, int s, int t, int l, int r) {
    // [l,r] is the query range
    if (s > r || t < l) {
        return -1;
    }
    if (s >= l && t <= r) { // return idx of the rightmost nonzero element in [s,t]
        return d[p].second;      
    }
    int mid = s + (t-s)/2;
    int right_result = _query_left(2*p + 1, mid + 1, t, l, r);
    return right_result==-1?_query_left(2 * p, s, mid, l, r):right_result;
}
int _query_right(int p, int s, int t, int l, int r) {
    // [l,r] is the query range
    if (s > r || t < l) {
        return -1;
    }
    if (s >= l && t <= r) {
        return d[p].first;      
    }
    int mid = s + (t-s)/2;
    int left_result = _query_right(2 * p, s, mid, l, r);
    return left_result==-1?_query_right(2 * p + 1, mid + 1, t, l, r):left_result;
}
void update(int idx, int x) {
    if(idx > H){
        return;
    }
    diff[idx] += x;  // Add x to the current value
    _update(idx, diff[idx]==0, 1, H, 1);
}
int query_left(int k) {
    if(k==1){
        return -1;
    }
    return _query_left(1,1,H,1,k-1);
}
int query_right(int k) {
    if(k == curH){
        return -1;
    }
    return _query_right(1,1,H,k+1,curH);
}

void solve() {
    int n, h, k;
    cin >> n;
    for(int i =1;i<=n;++i){
        cin >> h >> k; 
        H = max(H, h);
        s.pb(mp(h,k));
    }
    sort(s.begin(), s.end());
    memset(diff, 0, sf(diff));
    build(1, H, 1); // this is to prevent curH+1 from overflowing and causing p to refer to the wrong node
    update(1, 1);
    update(s[0].second + 1,-1);
    for(int j = 1; j<n;++j){
        // cout << j << e1 << query_right(2) << e2;
        h =s[j].first;
        k = s[j].second;
        curH = h;
        if(diff[curH -k +1] != 0){
            update(curH+1,-1);
            update(curH -k + 1, 1);
        }
        else{
            int A = query_left(curH -k+1); 
            int B = query_right(curH-k+1);
            A++;
            // cout << A << e1 << B << endl;
            if (B == -1){
                B = curH;
            }
            else{
                B--;
            }
            //cout << A << e1 << B << endl;
            update(curH+1,-1);
            update(A-1, 1);
            update(A+B-curH+k-1, -1);
            update(B+1, 1);
        }
        // for(int i = 1;i<=H;++i){
        //     cout << diff[i] << e1;
        // }
        // cout << e2;
    }
    ll ans = 0;
    ll cur = 0;
    for(int i = 1;i<=H;++i){
        cur += diff[i];
        ans += (cur-1)*cur;
    }
    cout<<ans/2<<endl;
}

void open_file() {
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
}
void prep(){
    
}
int main(void) {
    int t = 1;
    // open_file();
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cin >> t;
    prep();
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'void open_file()':
sails.cpp:187:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |     freopen("test.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:188:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |     freopen("test.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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