Submission #519556

#	Time	Username	Problem	Language	Result	Execution time	Memory
519556		XII	Sails (IOI07_sails)	C++17	5 / 100	665 ms	6124 KiB

sails

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

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI07_sails"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 1e5 + 1;
int n;
using pi = pair<int, int>;
pi a[N];
ll pref[N], ans;

int ST[N * 4], lz[N * 4];

void down(int id){
    ST[id * 2] += lz[id];
    ST[id * 2 + 1] += lz[id];
    lz[id * 2] += lz[id];
    lz[id * 2 + 1] += lz[id];
    lz[id] = 0;
}

void updRange(const int &l, const int &r, const int &v, int id = 1, int be = 1, int en = n){
    if(r < be || en < l) return;
    if(l <= be && en <= r){
        ST[id] += v;
        lz[id] += v;
        return;
    }
    int mi = (be + en) / 2;
    if(lz[id]) down(id);
    updRange(l, r, v, id * 2, be, mi);
    updRange(l, r, v, id * 2 + 1, mi + 1, en);
    ST[id] = max(ST[id * 2], ST[id * 2 + 1]);
}

int getPos(const int &v, const int &i, int id = 1, int be = 1, int en = n){
    if(i < be) return -1;
    if(be == en) return (ST[id] < v ? be : -1);
    int mi = (be + en) / 2;
    if(lz[id]) down(id);
    if(i <= mi) return getPos(v, i, id * 2, be, mi);
    if(ST[id * 2] < v) return max(mi, getPos(v, i, id * 2 + 1, mi + 1, en));
    return getPos(v, i, id * 2, be, mi);
}

void getAns(int id = 1, int be = 1, int en = n){
    if(be == en){
        ans += (pref[ST[id]] - ST[id]);
        return;
    }
    int mi = (be + en) / 2;
    getAns(id * 2, be, mi);
    getAns(id * 2 + 1, mi + 1, en);
}

bool check(const int &ti){
    memset(ST, 0, sizeof(ST));
    memset(lz, 0, sizeof(lz));
    FORU(i, 1, n){
        int p = getPos(ti, a[i].fi);
        if(p < a[i].se) return false;
        updRange(p - a[i].se + 1, p, 1);
    }
    return true;
}

int main(){
    IOS;
    Fi();
    cin >> n;
    FORU(i, 1, n) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1, greater<pi>());
    int l = 1, r = n, suit;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            suit = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    check(suit);
    FORU(i, 1, n) pref[i] = pref[i - 1] + i;
    getAns();
    cout << ans;
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'void Fi()':
sails.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10