| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 877709 | josanneo22 | Sails (IOI07_sails) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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')
int N, NN = 1 << 16, t[(1 << 16)) + 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];
});
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);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
smart();
}