Submission #429589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
429589	2021-06-16T07:21:54 Z	Hideo	Finding Routers (IOI20_routers)	C++17	100 / 100	3 ms	388 KB

routers

//#include "grader.cpp"
#include "routers.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define pi pair < int, int >

const int N = 1007;
const int INF = 1e9 + 7;

int t[4 * N], lz[4 * N];
int mx[N], pos[N];

void push (int v, int l, int r){
    if (l != r){
        lz[v + v] = min(lz[v], lz[v + v]);
        lz[v + v + 1] = min(lz[v], lz[v + v + 1]);
    }
    t[v] = min(t[v], lz[v]);
    lz[v] = INF;
}

void upd (int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if (ql <= l && r <= qr){
        lz[v] = min(lz[v], val);
        push(v, l, r);
        return;
    }
    if (r < ql || qr < l)
        return;
    int mid = (l + r) >> 1;
    upd(v + v, l, mid, ql, qr, val);
    upd(v + v + 1, mid + 1, r, ql, qr, val);
}

int get (int v, int l, int r, int pos){
    push(v, l, r);
    if (l == r)
        return t[v];
    else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return get(v + v, l, mid, pos);
        return get(v + v + 1, mid + 1, r, pos);
    }
}

std::vector<int> find_routers(int l, int n, int q) {
    memset(t, 0x3f3f3f3f, sizeof(t));
    memset(lz, 0x3f3f3f3f, sizeof(lz));
    upd(1, 0, n - 1, 0, n - 1, l);
    for (int i = 1; i < n; i++){
        int r = get(1, 0, n - 1, i - 1);
        //cout << i << ' ' << r << endl;
        for (int j = 20; j >= 0; j--){
            int v = mx[i - 1] + (1 << j);
            if (v < r){
                int x = use_detector(v);
                //cout << x << ' ' << v << endl;
                mx[x] = max(mx[x], v);
                upd(1, 0, n - 1, 0, x - 1, v);
            }
        }
        pos[i] = 2 * mx[i - 1] - pos[i - 1];
    }
    vector<int> ans;

    for (int i = 0; i < n; i++){
        ans.pb(pos[i]);
	}
	return ans;
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	388 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	3 ms	332 KB	Output is correct
5	Correct	2 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	3 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	3 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	3 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct