oj.uz

Submission #649253

# Submission time Handle Problem Language Result Execution time Memory
649253 2022-10-09T17:33:52 Z tbzard Sails (IOI07_sails) C++17
100 / 100
 87 ms 3656 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

int h[100005], k[100005];
pii p[100005];

ll ft[100005];
void update(int i, int v){
    for(;i<=100001;i+=(i&-i)) ft[i] += v;
}
ll query(int i){
    ll ans = 0;
    for(;i>0;i-=(i&-i)) ans+=ft[i];
    return ans;
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d", &h[i], &k[i]);
        p[i] = mp(h[i], k[i]);
    }
    sort(p+1, p+1+n);
    for(int i=1;i<=n;i++) {
        int h = p[i].fi, k = p[i].se;
        ll val = query(h-k+1);

        int l2 = h-k+1+1;
        int l1 = h-k+1;

        int l = 0, r = 0;
        int lo = 1, hi = l1;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(query(mid) == val) l = mid, hi = mid-1;
            else lo = mid+1;
        }

        lo = l1, hi = h;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(query(mid) == val) r = mid, lo = mid+1;
            else hi = mid-1;
        }

        int tot = r-l1+1;
        update(l, 1);
        update(l+tot, -1);

        update(r+1, 1);
        update(h+1, -1);
    }
    ll ans = 0;
    for(int i=1;i<=100000;i++){
        ll val = query(i);
        ans += val*(val-1);
    }
    printf("%lld\n", ans/2);
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:41:13: warning: unused variable 'l2' [-Wunused-variable]
   41 |         int l2 = h-k+1+1;
      |             ^~
sails.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sails.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d%d", &h[i], &k[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 724 KB Output is correct
2 Correct 21 ms 1100 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1984 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3080 KB Output is correct
2 Correct 63 ms 3168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3528 KB Output is correct
2 Correct 48 ms 3016 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3656 KB Output is correct
2 Correct 53 ms 3132 KB Output is correct