oj.uz

답안 #519556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519556 2022-01-26T16:30:36 Z XII Sails (IOI07_sails) C++17
5 / 100
 665 ms 6124 KB 
#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

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Incorrect 2 ms 3388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3444 KB Output is correct
2 Incorrect 2 ms 3404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 168 ms 4128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 4764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 5492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 5828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 665 ms 6124 KB Output isn't correct
2 Halted 0 ms 0 KB -