Submission #159782

#TimeUsernameProblemLanguageResultExecution timeMemory
159782karmaSails (IOI07_sails)C++14
100 / 100
105 ms3192 KiB
#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) + 5; 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; //cout << l << ' ' << r << '\n'; 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); /// t1 >= t2 >= t3 >= ... >= tn for(int i = 1; i <= n; ++i) { x = Get(a[i].fi - a[i].se + 1); low = 1, high = a[i].fi - a[i].se + 1; while(low <= high) { mid = (low + high) >> 1; if(Get(mid) > x) low = mid + 1; else high = mid - 1; } pos = low, low = a[i].fi - a[i].se + 1, high = a[i].fi; while(low <= high) { mid = (low + high) >> 1; if(Get(mid) == x) low = mid + 1; else high = mid - 1; } Update(low, a[i].fi, 1); /// a[i].fi - a[i].se + 1 -> a[i].fi /// a[i].fi - a[i].se + 1 -> low - 1, low -> a[i].fi Update(pos, pos + low - (a[i].fi - a[i].se + 1) - 1, 1); } ll res = 0; for(int i = N - 1; i >= 1; --i) { x = Get(i); res += 1ll * x * (x - 1) / 2; } cout << res; }

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:30:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:31:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".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...