oj.uz

Submission #62810

# Submission time Handle Problem Language Result Execution time Memory
62810 2018-07-30T06:55:36 Z kdh9949 허수아비 (JOI14_scarecrows) C++17
100 / 100
 243 ms 79880 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second

const int N = 200005, inf = int(2e9);

int n, ac, bc;
pii a[N], b[N], as[N], bs[N];

ll f(int s, int e){
    if(s == e){
        b[s] = a[s];
        return 0;
    }
    int m = (s + e) / 2;
    ll r = f(s, m) + f(m + 1, e);
    int p, q, cc = s;
    as[0] = {inf, -inf}; bs[0] = {-inf, -inf + 1};
    ac = bc = 1;
    for(p = s, q = m + 1; p <= m || q <= e; ){
        if(q > e || (p <= m && b[p].Y < b[q].Y)){
            a[cc++] = b[p];
            while(as[ac - 1].X < b[p].X) ac--;
            as[ac++] = b[p++];
        }
        else{
            a[cc++] = b[q];
            while(bs[bc - 1].X > b[q].X) bc--;
            r += int(as + ac -
                    lower_bound(as, as + ac, bs[bc - 1], [](pii p, pii q){
                        return p.Y < q.Y;
                    }));
            bs[bc++] = b[q++];
        }
    }
    for(int i = s; i <= e; i++) b[i] = a[i];
    return r;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &a[i].X, &a[i].Y);
    }
    sort(a, a + n);
    printf("%lld\n", f(0, n - 1));
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].X, &a[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 2 ms 756 KB Output is correct
8 Correct 4 ms 756 KB Output is correct
9 Correct 2 ms 756 KB Output is correct
10 Correct 3 ms 756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 988 KB Output is correct
2 Correct 7 ms 1032 KB Output is correct
3 Correct 7 ms 1132 KB Output is correct
4 Correct 7 ms 1228 KB Output is correct
5 Correct 7 ms 1328 KB Output is correct
6 Correct 8 ms 1428 KB Output is correct
7 Correct 8 ms 1528 KB Output is correct
8 Correct 5 ms 1700 KB Output is correct
9 Correct 7 ms 1796 KB Output is correct
10 Correct 8 ms 1952 KB Output is correct
11 Correct 9 ms 2052 KB Output is correct
12 Correct 7 ms 2052 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8464 KB Output is correct
2 Correct 227 ms 11604 KB Output is correct
3 Correct 189 ms 16172 KB Output is correct
4 Correct 150 ms 20024 KB Output is correct
5 Correct 163 ms 23188 KB Output is correct
6 Correct 168 ms 26976 KB Output is correct
7 Correct 180 ms 30872 KB Output is correct
8 Correct 223 ms 34876 KB Output is correct
9 Correct 171 ms 39364 KB Output is correct
10 Correct 182 ms 42556 KB Output is correct
11 Correct 183 ms 46304 KB Output is correct
12 Correct 230 ms 50316 KB Output is correct
13 Correct 216 ms 54320 KB Output is correct
14 Correct 162 ms 58668 KB Output is correct
15 Correct 212 ms 61924 KB Output is correct
16 Correct 224 ms 66008 KB Output is correct
17 Correct 142 ms 67264 KB Output is correct
18 Correct 217 ms 72452 KB Output is correct
19 Correct 243 ms 76280 KB Output is correct
20 Correct 206 ms 79880 KB Output is correct