# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
159778 | 2019-10-24T14:30:12 Z | karma | Sails (IOI07_sails) | C++14 | 98 ms | 3468 KB |
#include<bits/stdc++.h> #define FileName "test" #define ll long long #define pb emplace_back #define fi first #define se second #define mp make_pair using namespace std; typedef pair<ll, ll> pii; const int N = int(1e5) + 1; const ll oo = (ll)1e18; int n, x, low, pos, high, mid; pii a[N]; int t[N]; void Update(int x, int val) {for(; x < N; x += (x & -x)) t[x] += val;} int Get(int x) {int res = 0; for(; x > 0; x -= (x & -x)) res += t[x]; return res;} void Update(int l, int r, int val) { if(l > r) return; Update(l, val); Update(r + 1, -val); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(FileName".inp", "r")) { freopen(FileName".inp", "r", stdin); freopen(FileName".out", "w", stdout); } cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se; sort(a + 1, a + n + 1, greater<pii>()); for(int i = 1; i <= n; ++i) { if(a[i].se == 0) continue; //cout << a[i].fi << ' ' << a[i].se << ' '; x = Get(a[i].se), low = a[i].se, high = a[i].fi; while(low <= high) { mid = (low + high) >> 1; if(Get(mid) == x) low = mid + 1; else high = mid - 1; } pos = high, low = 1, high = a[i].se; //cout << pos << ' '; while(low <= high) { mid = (low + high) >> 1; if(Get(mid) < x) low = mid + 1; else high = mid - 1; } Update(pos - a[i].se + low, pos, 1); Update(1, high, 1); //cout << high << ' '; //cout << pos - a[i].se + low << ' ' << pos << '\n'; } ll res = 0; for(int i = N - 1; i >= 1; --i) { x = Get(i); //if(i < 6) cout << x << ' '; res += 1ll * x * (x - 1) / 2; } cout << res; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 248 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 24 ms | 1272 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 47 ms | 1960 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 82 ms | 2828 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 89 ms | 3216 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 98 ms | 3468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |