Submission #634510

#	Time	Username	Problem	Language	Result	Execution time	Memory
634510		MohamedFaresNebili	Sails (IOI07_sails)	C++14	65 / 100	324 ms	5844 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10