Submission #429589

#	Time	Username	Problem	Language	Result	Execution time	Memory
429589		Hideo	Finding Routers (IOI20_routers)	C++17	100 / 100	3 ms	388 KiB

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 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 40 / 40