Submission #877707

#	Time	Username	Problem	Language	Result	Execution time	Memory
877707		josanneo22	Sails (IOI07_sails)	C++17	100 / 100	39 ms	3152 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;

namespace fast {
#pragma GCC optimize(Ofast)
#pragma GCC optimization (unroll-loops)
#pragma GCC target(avx,avx2,fma)
#pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
}
using namespace fast;

inline string read_string() {
    char ch = getchar(); string st1 = "";
    while (!((ch >= 'A') && (ch <= 'Z'))) ch = getchar();
    while ((ch >= 'A') && (ch <= 'Z'))  st1 += ch, ch = getchar();
    return st1;
}

template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
#define sp putchar(' ')
#define nl putchar('\n')
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() {

    re(N);

    vector<int> flags(N), height(N);
    for (int i = 0; i < N; i++)
        re(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, 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;
    }
    ps(ans);
    //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)
      | 
sails.cpp:14: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   14 | #pragma GCC optimization (unroll-loops)
      | 
sails.cpp:13:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
   13 | #pragma GCC optimize(Ofast)
      |                      ^~~~~
sails.cpp:15:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   15 | #pragma GCC target(avx,avx2,fma)
      |                    ^~~
sails.cpp:16:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   16 | #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
      |                    ^~~
sails.cpp:36:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   36 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
sails.cpp:43:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   43 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
sails.cpp:45:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
sails.cpp:59:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   59 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
sails.cpp:65:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   65 | inline string read_string() {
      |                           ^
sails.cpp:65:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:65:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:65:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:72:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
      |                                         ^
sails.cpp:72:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:72:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:72:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:73:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   73 | template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
      |                                                         ^
sails.cpp:73:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:73:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:73:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:74:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   74 | template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
      |                                        ^
sails.cpp:74:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:74:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:74:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:75:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   75 | template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
      |                                                         ^
sails.cpp:75:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:75:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:75:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:78:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   78 | void stupid() {
      |             ^
sails.cpp:78:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:78:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:78:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp: In function 'void stupid()':
sails.cpp:92:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   92 |     sort(ord.begin(), ord.end(), [&](int x, int y) {
      |                                                  ^
sails.cpp:92:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:92:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:92:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp: At global scope:
sails.cpp:111:29: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  111 | void modify(int i, int delta) {
      |                             ^
sails.cpp:111:29: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:111:29: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:111:29: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:114:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  114 | int query(int i) {
      |                ^
sails.cpp:114:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:114:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:114:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:119:15: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  119 | int find(int x) {
      |               ^
sails.cpp:119:15: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:119:15: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:119:15: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp:131:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  131 | void smart() {
      |            ^
sails.cpp:131:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:131:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:131:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp: In function 'void smart()':
sails.cpp:141:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  141 |     sort(ord.begin(), ord.end(), [&](int x, int y) {
      |                                                  ^
sails.cpp:141:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:141:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:141:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sails.cpp: At global scope:
sails.cpp:168:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  168 | int main() {
      |          ^
sails.cpp:168:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sails.cpp:168:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sails.cpp:168:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• 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