제출 #1352119

#제출 시각아이디문제언어결과실행 시간메모리
1352119vjudge1Sails (IOI07_sails)C++20
100 / 100
55 ms1476 KiB
#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(FNAME".inp","r")){
        freopen(FNAME".inp","r",stdin);
        freopen(FNAME".out","w",stdout);
    }
}

template<typename T>
struct FenwickTree{
    int n;
    vector<T> bit;
    FenwickTree(int N=0){
        n=N;
        if (n>0){
            bit.resize(n+1,0);
        }
    }
    void update(int node,T val){
        while (node<=n){
            bit[node]+=val;
            node += (node & -node);
        }
    }
    T getVal(int node){
        T res=0;
        while (node>0){
            res+=bit[node];
            node -= (node & -node);
        }
        return res;
    }
    // Into difference BIT
    inline void range(int l,int r,T val){
        update(l,+val);
        if (r+1<=n) update(r+1,-val);
    }
    inline T getRange(int l,int r){
        return getVal(r) - getVal(l-1); 
    }
};

int n;
vector<pair<int,int>> a;
int MAXH;

void init(){
    cin>>n;
    a.resize(n);
    for (auto &x : a) cin>>x.first>>x.second, maximize(MAXH, x.first);
    sort(allof(a));
    MAXH++;
}

inline long long nC2(long long x){
    return x * (x - 1) / 2ll;
}

void sol(){
    FenwickTree<int> bit(MAXH);

    auto getThres = [&] (int x,int h) -> int {
        int l = 1, r = h;
        int res = 0;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (bit.getVal(mid) >= x){
                res = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        return res;
    };

    // * take last k sails to avoid congestion
    for (const auto &[h, k] : a){
        int v = bit.getVal(h - k + 1);
        int R = getThres(v, h);
        int L = getThres(v + 1, h);
        bit.range(R + 1, h, 1);
        int leftover = h - R;
        bit.range(L + 1, L + (k - h + R), 1);
    }

    long long res = 0;
    for (int i = 0; i < MAXH; i++){
        res += nC2(bit.getVal(i));
    }
    cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

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

sails.cpp: In function 'void setup()':
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(FNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(FNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...