Submission #1316429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316429		pvpro	Tower (JOI24_tower)	C++20	0 / 100	56 ms	22232 KiB

Main

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

struct Node {
	Node *l, *r;
	int mn, mx;
	Node() {
		l = nullptr;
		r = nullptr;
		mn = -1e18;
		mx = -1e18;
	}
};

void updateMx(Node *root, int l, int r, int ql, int qr, int x) {
	if (root->mn >= x || l >= qr || r <= ql) {
		return;
	}
	if (ql <= l && r <= qr && root->mx <= x) {
		root->mx = x;
		root->mn = x;
	} else {
		int m = (l + r) / 2;
		if (root->l == nullptr) {
			root->l = new Node();
			root->r = new Node();
		}
		if (root->mn == root->mx) {
			root->l->mn = root->mn;
			root->r->mn = root->mn;
			root->l->mx = root->mn;
			root->r->mx = root->mn;
		}
		updateMx(root->l, l, m, ql, qr, x);
		updateMx(root->r, m, r, ql, qr, x);
		root->mn = min(root->l->mn, root->r->mn);
		root->mx = max(root->l->mx, root->r->mx);
	}
}

int get(Node *root, int l, int r, int ql, int qr) {
	if (l >= qr || r <= ql || root->mn > root->mx) {
		return -1e18;
	}
	if (root->mx <= root->mn) {
		return root->mx;
	}
	int m = (l + r) / 2;
	return max(get(root->l, l, m, ql, qr), get(root->r, m, r, ql, qr));
}

void solve() {
    int n, q;
	int d, a, b;
	cin >> n >> q;
	cin >> d >> a >> b;
	b = min(b, a * d);
	int lst = 0;
    vector<int> can(1000100);
    vector<int> dp(1000100, 1e18);
    dp[0] = 0;
	vector<pii> seg;
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		++r;
        for (int j = l; j < r; ++j) {
            can[j] = 1;
        }
	}
    for (int i = 1; i < 1000100; ++i) {
        if (!can[i]) {
            dp[i] = dp[i - 1] + a;
            if (i >= d){
                dp[i] = min(dp[i], dp[i - d] + b);
            }
        }
    }
	seg.pb(mp(lst, ((int)1e12) + 1));
	vector<int> ans(q, -1);
	vector<pii> quests(q);
	for (int i = 0; i < q; ++i) {
		int x;
		cin >> x;
        if (dp[x] >= 1e18) {
            cout << -1 << endl;
        } else {
            cout << dp[x] << endl;
        }
	}
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32