Submission #877700

#	Time	Username	Problem	Language	Result	Execution time	Memory
877700		josanneo22	Sails (IOI07_sails)	C++17	100 / 100	44 ms	3164 KiB

sails

/*
Problem: IOI 2007 Sails
When:    2023-11-16 14:54:19
Author:  Ning07
*/

#pragma warning(suppress : 4996)
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

void stupid() {
    int N; cin >> N;
    vector<int> flags(N), height(N);
    multiset<pair<i64, int>> S;
    int mh = 0; vector<int> mx(2e5 + 500);
    for (int i = 0; i < N; i++) {
        cin >> height[i] >> flags[i];
        mh = max(mh, height[i]);
        mx[1]++; mx[height[i] + 1]--;
    }
    for (int i = 1; i <= mh; i++) mx[i] += mx[i - 1];
    for (int i = 1; i <= mh; i++) if (mx[i] != 0) S.insert(make_pair(0, i));
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        return height[x] < height[y];
        });
    for (int p = 0; p < N; p++) {
        int i = ord[p];
        multiset<pair<i64, int>> copy;
        int cnt = flags[i];
        for (auto& v : S) {
            if (v.second >= height[i] + 1) copy.insert(make_pair(v.first, v.second));
            else if (mx[v.second] == v.first) copy.insert(make_pair(v.first, v.second));
            else if (cnt) { cnt--; copy.insert(make_pair(v.first + 1, v.second)); }
            else copy.insert(make_pair(v.first, v.second));
        } swap(S, copy);
    }
    i64 ans = 0;
    for (auto& v : S) ans += (v.first) * (v.first - 1) / 2;
    cout << ans << '\n';
}
int N,NN=1<<17,t[(1<<17)+5];
void modify(int i,int delta){
    for(;i<=NN;i+=i&-i) t[i]+=delta;
}
int query(int i){
    int sum=0;
    for(;i;i-=i&-i) sum+=t[i];
    return sum;
}
int find(int x){
    int pos=0;
    for(int i=NN;i;i>>=1){
        int j=pos+i;
        if(j<=NN && t[j]>=x){
            pos=j;
            x-=t[j];
        }
    }
    return pos;
}

void smart() {

    cin >> N;

    vector<int> flags(N), height(N);
    for (int i = 0; i < N; i++)
        cin >> height[i] >> flags[i];

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        return height[x] < height[y];
    });
    /*  假设现在的序列为6 6 6 5 5 4 2 1
        flag = 4
        我们加上了这个6 6 5 6 5 3 2
        但是同样的我们可以 6 6 6 5 5 3 2
        让第一个k大的是l,最后是r,
        需要加上的是need=height[i]-r
        需要加上的区间[l,l+need], [r+1,height[i]]
    */
    for (int x = 0; x < N; x++) {
        int i = ord[x];
        int pos = height[i] - flags[i] + 1;
        int val = query(pos);
        int l = find(val + 1) + 1;
        int r = (val == 0) ? height[i] : find(val);
        modify(l, 1);   modify(l + r - pos + 1, -1);
        modify(r + 1, 1); modify(height[i] + 1, -1);
    }
    i64 ans = 0;
    for (int i = 1; i <= height[ord[N - 1]]; i++) {
        i64 t = query(i);
        ans += t * (t - 1) / 2;
    }
    cout << ans << '\n';
    //cout << get(1) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    //stupid();
    smart();
}

Compilation message (stderr)

sails.cpp:7: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    7 | #pragma warning(suppress : 4996)
      |

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