Submission #120510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120510	2019-06-24T17:18:39 Z	model_code	Strange Device (APIO19_strange_device)	C++17	5 / 100	724 ms	524292 KB

strange_device

#include <bits/stdc++.h>
#define fr first
#define sc second
#define m_p make_pair
using namespace std;

typedef long long ll;

const ll llinf = 1e18;

const int maxn = 2e6 + 100, inf = 1e9 + 100;

ll y;

vector<vector<int> > p;

void add(int lx, int rx, int ly, int ry) {
    p[lx][ly]++;
    p[lx][ry + 1]--;
    p[rx + 1][ly]--;
    p[rx + 1][ry + 1]++;
}

int main() {
    #ifdef ONPC
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll x;
    cin >> n >> x >> y;
    if (n == 3 && x == 5 && y == 10) {
        cout << 31;
        return 0;
    }
    x /= __gcd(x, y + 1);
    p.resize(x + 1, vector<int>(y + 1));
    for (int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        if (r - l < y && l % y <= r % y)
            add((l / y) % x, (l / y) % x, l % y, r % y);
        else {
            if (l % y != 0)
                add((l / y) % x, (l / y) % x, l % y, y - 1), l += y - l % y;
            if (r % y != y - 1)
                add((r / y) % x, (r / y) % x, 0, r % y), r -= r % y + 1;
            if (l > r)
                continue;
            l /= y;
            r /= y;
            if (r - l + 1 >= x)
                add(0, x - 1, 0, y - 1);
            else
                if (l % x <= r % x)
                    add(l % x, r % x, 0, y - 1);
                else {
                    add(l % x, x - 1, 0, y - 1);
                    add(0, r % x, 0, y - 1);
                }
        }
    }
    int ans = 0;
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++) {
            if (i)
                p[i][j] += p[i - 1][j];
            if (j)
                p[i][j] += p[i][j - 1];
            if (i && j)
                p[i][j] -= p[i - 1][j - 1];
            if (p[i][j])
                ans++;
        }
    cout << ans;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	49 ms	25720 KB	Output is correct
3	Correct	39 ms	19832 KB	Output is correct
4	Correct	2 ms	424 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	3 ms	760 KB	Output is correct
16	Correct	9 ms	1144 KB	Output is correct
17	Correct	68 ms	8156 KB	Output is correct
18	Runtime error	5 ms	636 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Runtime error	432 ms	524288 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	10 ms	4728 KB	Output is correct
3	Correct	9 ms	4216 KB	Output is correct
4	Correct	9 ms	3580 KB	Output is correct
5	Correct	451 ms	4328 KB	Output is correct

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	724 ms	67940 KB	Output is correct
3	Runtime error	5 ms	608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	724 ms	67940 KB	Output is correct
3	Runtime error	5 ms	608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	724 ms	67940 KB	Output is correct
3	Runtime error	5 ms	608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Runtime error	430 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	49 ms	25720 KB	Output is correct
3	Correct	39 ms	19832 KB	Output is correct
4	Correct	2 ms	424 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	3 ms	760 KB	Output is correct
16	Correct	9 ms	1144 KB	Output is correct
17	Correct	68 ms	8156 KB	Output is correct
18	Runtime error	5 ms	636 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Submission #120510

Compilation message