oj.uz

Submission #634510

# Submission time Handle Problem Language Result Execution time Memory
634510 2022-08-24T13:46:57 Z MohamedFaresNebili Sails (IOI07_sails) C++14
65 / 100
 324 ms 5844 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, C + N, 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 7 ms 340 KB Output is correct
2 Correct 7 ms 356 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1928 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 3040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 5100 KB Output is correct
2 Correct 207 ms 5160 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 5464 KB Output is correct
2 Correct 113 ms 4484 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 5844 KB Output is correct
2 Correct 174 ms 4364 KB Output is correct