제출 #1355665

#제출 시각아이디문제언어결과실행 시간메모리
1355665po_rag526Sails (IOI07_sails)C++17
100 / 100
110 ms5920 KiB
#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define len(a) int((a).size())
#define ll long long
#define name ""
using namespace std;

void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void file(){
    if(fopen(name ".inp", "r")){
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
}

struct node{
    int lz, mx, mn;
};

vector <node> st;
vector <pair <int, int>> a;
int n, mx_n;

void inp(){
    cin >> n;
    a.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin() + 1, a.begin() + 1 + n);
    mx_n = a[n].first;
    st.assign(4*mx_n + 7, {0, 0, 0});
}

void down(int id){
    int val = st[id].lz;
    if(val == 0) return;
    st[id].lz = 0;
    st[2*id].lz += val;
    st[2*id].mx += val;
    st[2*id].mn += val;
    st[2*id + 1].lz += val;
    st[2*id + 1].mx += val;
    st[2*id + 1].mn += val;
}

node get_in4(int id, int l, int r, int u, int v){
    if(v < l || r < u) return {0, 0, (int)1e9};
    if(u <= l && r <= v) return st[id];
    down(id);
    int mid = (l + r)/2;
    node get1 = get_in4(2*id, l, mid, u, v);
    node get2 = get_in4(2*id + 1, mid + 1, r, u, v);
    return {0, max(get1.mx, get2.mx), min(get1.mn, get2.mn)};
}

int get_pos(int id, int l, int r, int u, int v, int val){
    if(v < l || r < u) return -1;
    if(st[id].mn > val) return -1;
    if(l == r) return l;
    down(id);
    int mid = (l + r)/2;
    int get1 = get_pos(2*id, l, mid, u, v, val);
    if(get1 == -1) get1 = get_pos(2*id + 1, mid + 1, r, u, v, val);
    return get1;
}

void update(int id, int l, int r, int u, int v){
    if(v < l || r < u) return;
    if(u <= l && r <= v){
        st[id].lz += 1;
        st[id].mx += 1;
        st[id].mn += 1;
        return;
    }
    down(id);
    int mid = (l + r)/2;
    update(2*id, l, mid, u, v);
    update(2*id + 1, mid + 1, r, u, v);
    st[id].mx = max(st[2*id].mx, st[2*id + 1].mx);
    st[id].mn = min(st[2*id].mn, st[2*id + 1].mn);
}

int get_ans(int id, int l, int r, int pos){
    if(pos < l || pos > r) return -1;
    if(l == r) return st[id].mx;
    down(id);
    int mid = (l + r)/2;
    int get1 = get_ans(2*id, l, mid, pos);
    int get2 = get_ans(2*id + 1, mid + 1, r, pos);
    return max(get1, get2);
}

ll calc(ll num){
    return (num*(num+1))/2;
}

void solve(){
    inp();
    for(int i = 1; i <= n; i++){
        int cur_pos = a[i].first - a[i].second + 1;
        node in4 = get_in4(1, 1, mx_n, cur_pos, a[i].first);
        if(in4.mx != in4.mn){
            int pos = get_pos(1, 1, mx_n, 1, a[i].first, in4.mx - 1);
            update(1, 1, mx_n, pos, a[i].first);
            int rest = a[i].second - (a[i].first - pos + 1);
            pos = get_pos(1, 1, mx_n, 1, a[i].first, in4.mx);
            update(1, 1, mx_n, pos, pos + rest - 1);
        }
        else{
            int pos = get_pos(1, 1, mx_n, 1, a[i].first, in4.mx);
            update(1, 1, mx_n, pos, pos + a[i].second - 1);
        }
    }
    ll ans = 0;
    for(int i = 1; i <= mx_n; i++){
        int num = get_ans(1, 1, mx_n, i);
        ans += calc(1LL*num - 1);
    }
    cout << ans << '\n';
}

int main(){
    fastio();
    file();
    solve();
    return 0;
}

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

sails.cpp: In function 'void file()':
sails.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…