oj.uz

Submission #159782

# Submission time Handle Problem Language Result Execution time Memory
159782 2019-10-24T15:07:46 Z karma Sails (IOI07_sails) C++14
100 / 100
 105 ms 3192 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) + 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

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);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 760 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 24 ms 1144 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1864 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2932 KB Output is correct
2 Correct 72 ms 2764 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3192 KB Output is correct
2 Correct 53 ms 2896 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 2300 KB Output is correct
2 Correct 63 ms 3044 KB Output is correct