oj.uz

Submission #555238

# Submission time Handle Problem Language Result Execution time Memory
555238 2022-04-30T10:05:01 Z tht2005 Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 2 ms 1876 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct pt {
    int x, y;
    pt(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
};

bool ccw(const pt& a, const pt& b, const pt& c) {
    return (LL)(b.x - a.x) * (c.y - b.y) - (LL)(c.x - b.x) * (b.y - a.y) > 0;
}

const int N = 100005;
int n, m, n1, n2, a[N], b[N];
double x[N], y[N];
LL res;
pt l1[N], l2[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        pt nw(i, a[i]);
        while(n1 > 1 && !ccw(l1[n1 - 2], l1[n1 - 1], nw)) --n1;
        l1[n1++] = nw;
    }
    for(int i = 0; i < m; ++i) {
        scanf("%d", b + i);
        pt nw(i, b[i]);
        while(n2 > 1 && !ccw(l2[n2 - 2], l2[n2 - 1], nw)) --n2;
        l2[n2++] = nw;
    }
    for(int i = 1; i < n1; ++i) {
        x[i] = (l1[i].y - l1[i - 1].y) / (l1[i].x - l1[i - 1].x);
    }
    for(int i = 1; i < n2; ++i) {
        y[i] = (l2[i].y - l2[i - 1].y) / (l2[i].x - l2[i - 1].x);
    }

    /*
    for(int i = 0; i < n1; ++i) {
        printf("%d %d %.5lf\n", l1[i].x, l1[i].y, x[i]);
    }
    puts("=========================");
    for(int i = 0; i < n2; ++i) {
        printf("%d %d %.5lf\n", l2[i].x, l2[i].y, y[i]);
    }
    return 0;
    */

    for(int i = n1 - 1, j = n2 - 1; i || j; ) {
        if(i != 0 && (j == 0 || x[i] >= y[j])) {
            res += (LL)l2[j].y * (l1[i].x - l1[i - 1].x);
            --i;
        }
        else {
            res += (LL)l1[i].y * (l2[j].x - l2[j - 1].x);
            --j;
        }
    }
    printf("%lld", res);
    return 0;
}

Compilation message

kyoto.cpp: In function 'int main()':
kyoto.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d", a + i);
      |         ~~~~~^~~~~~~~~~~~~
kyoto.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d", b + i);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1800 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 1 ms 1876 KB Output is correct
20 Correct 1 ms 1876 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 1 ms 1876 KB Output is correct
24 Correct 1 ms 1876 KB Output is correct
25 Correct 1 ms 1876 KB Output is correct
26 Correct 1 ms 1876 KB Output is correct
27 Correct 2 ms 1876 KB Output is correct
28 Correct 1 ms 1876 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Incorrect 1 ms 1876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1800 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 1 ms 1876 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 1 ms 1876 KB Output is correct
20 Correct 1 ms 1876 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 1 ms 1876 KB Output is correct
24 Correct 1 ms 1876 KB Output is correct
25 Correct 1 ms 1876 KB Output is correct
26 Correct 1 ms 1876 KB Output is correct
27 Correct 2 ms 1876 KB Output is correct
28 Correct 1 ms 1876 KB Output is correct
29 Correct 1 ms 1876 KB Output is correct
30 Correct 1 ms 1876 KB Output is correct
31 Incorrect 1 ms 1876 KB Output isn't correct
32 Halted 0 ms 0 KB -