제출 #1355275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355275		minh201643	Sails (IOI07_sails)	C++20	100 / 100	133 ms	7288 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define file
#define debug(x) cerr << #x << " = " << x << '\n'

int n, sz;
pair<int, int> p[maxn];

struct node {
    ll sum, lz, mi;
}t[maxn * 4];

void push (int id, int l, int r) {
    if (t[id].lz != 0) {
        int mid = (l + r) >> 1;

        t[id * 2].sum += (mid - l + 1) * t[id].lz;
        t[id * 2 + 1].sum += (r - mid) * t[id].lz;

        t[id * 2].mi += t[id].lz;
        t[id * 2 + 1].mi += t[id].lz;

        t[id * 2].lz += t[id].lz;
        t[id * 2 + 1].lz += t[id].lz;
    }
    t[id].lz = 0;
}
void update (int id, int l, int r, int u, int v) {
    if (u > r || l > v) return ;
    if (u <= l && r <= v) {
        t[id].sum += (r - l + 1);
        t[id].lz += 1;
        t[id].mi += 1;
        return ;
    }

    int mid = (l + r) >> 1;
    push (id, l, r);

    update (id * 2, l, mid, u, v);
    update (id * 2 + 1, mid + 1, r, u, v);

    t[id].sum = t[id * 2].sum + t[id * 2 + 1].sum;
    t[id].mi = min (t[id * 2].mi, t[id * 2 + 1].mi);
}
int getpos (int id, int l, int r, int v, int x) {
    if (l > v || t[id].mi > x) return -1;
    if (l == r) return l;

    int mid = (l + r) >> 1;
    push (id, l, r);
    int res = -1;

    if (t[id * 2].mi <= x) res = getpos (id * 2, l, mid, v, x);
    if (res == -1) res = getpos (id * 2 + 1, mid + 1, r, v, x);

    return res;
}
ll getsum (int id, int l, int r, int u, int v) {
    if (u > r || l > v) return 0;
    if (u <= l && r <= v) return t[id].sum;

    int mid = (l + r) >> 1;
    push (id, l, r);

    return getsum (id * 2, l, mid, u, v) + getsum (id * 2 + 1, mid + 1, r, u, v);
}

void read() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second, sz = max (sz, p[i].first);
}

void solve() {
    sort (p + 1, p + n + 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int h = p[i].first, k = p[i].second;
        int r = h, l = r - k + 1;

        ll val_l = getsum (1, 1, sz, l, l), val_r = getsum (1, 1, sz, r, r);
        ll cur = 0, len = r - l + 1;

        if (val_l != val_r) {
            int pos = getpos (1, 1, sz, r, val_l - 1);

            cur += getsum (1, 1, sz, pos, r);
            update (1, 1, sz, pos, r);
            len -= r - pos + 1;
        }

        if (len > 0) {
            int pos = getpos (1, 1, sz, r, val_l);
            cur += getsum (1, 1, sz, pos, pos + len - 1);
            update (1, 1, sz, pos, pos + len - 1);
        }

        ans += cur;
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    if (fopen(file".INP","r")) {
        freopen(file".INP","r",stdin);
        freopen(file".OUT","w",stdout);
    }

    read();
    solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sails.cpp: In function 'int main()':
sails.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(file".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sails.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(file".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 5 / 5
• 서브태스크 2: 10 / 10
• 서브태스크 3: 10 / 10
• 서브태스크 4: 5 / 5
• 서브태스크 5: 10 / 10
• 서브태스크 6: 10 / 10
• 서브태스크 7: 10 / 10
• 서브태스크 8: 10 / 10
• 서브태스크 9: 10 / 10
• 서브태스크 10: 10 / 10
• 서브태스크 11: 10 / 10