oj.uz

Submission #634511

# Submission time Handle Problem Language Result Execution time Memory
634511 2022-08-24T13:48:18 Z MohamedFaresNebili Sails (IOI07_sails) C++14
100 / 100
 327 ms 4672 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
            using namespace std;
 
            using ll = long long;
            using ld = long double;
 
            #define int ll
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int MX = 100000;
 
            int N, H[100005], W[100005];
            int C[100005], ST[400005];
            void update(int v, int l, int r, int lo, int hi, int val) {
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    ST[v] += val; return;
                }
                update(v * 2, l, (l + r) / 2, lo, hi, val);
                update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
            }
            int query(int v, int l, int r, int p) {
                if(l == r) return ST[v];
                int md = (l + r) / 2;
                if(p <= md) return ST[v] + query(v * 2, l, (l + r) / 2, p);
                return ST[v] + query(v * 2 + 1, (l + r) / 2 + 1, r, p);
            }
            int findL(int v) {
                int lo = 1, hi = v, res = v;
                int K = query(1, 1, MX, v);
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    if(query(1, 1, MX, md) == K)
                        res = md, hi = md - 1;
                    else lo = md + 1;
                }
                return res;
            }
            int findR(int u, int v) {
                int lo = u, hi = v, res = u;
                int K = query(1, 1, MX, u);
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    if(query(1, 1, MX, md) == K)
                        res = md, lo = md + 1;
                    else hi = md - 1;
                }
                return res;
            }
            bool compare(int A, int B) {
                if(H[A] != H[B])
                    return H[A] < H[B];
                return W[A] < W[B];
            }
 
            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N;
                for(int l = 1; l <= N; l++)
                    cin >> H[l] >> W[l], C[l] = l;
                sort(C + 1, C + N + 1, compare);
                for(int e = 1; e <= N; e++) {
                    int i = C[e];
                    int lo = H[i] - W[i] + 1, hi = H[i];
                    int l = findL(lo), r = findR(lo, hi);
                    if(l == lo) update(1, 1, MX, lo, hi, 1);
                    else {
                        update(1, 1, MX, l, l + (W[i] - hi + r) - 1, 1);
                        update(1, 1, MX, r + 1, hi, 1);
                    }
                }
                int res = 0;
                for(int l = 1; l <= MX; l++) {
                    int K = query(1, 1, MX, l);
                    res += (K * (K - 1)) / 2;
                }
                cout << res << "\n";
                return 0;
            }

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 11 ms 2328 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1036 KB Output is correct
2 Correct 71 ms 1396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1572 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2584 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 4108 KB Output is correct
2 Correct 207 ms 4128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 4456 KB Output is correct
2 Correct 120 ms 3784 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 4672 KB Output is correct
2 Correct 171 ms 3308 KB Output is correct