Submission #1146336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146336		thieunguyenhuy	Floppy (RMI20_floppy)	C++20	100 / 100	64 ms	4680 KiB

floppy

#ifndef hwe
	#include "floppy.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T1, class T2> T1 random(T1 l, T2 r) {
    return uniform_int_distribution<T1>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e6 + 5, LG = 18;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

vector<int> pre[LG];

#ifdef hwe
void save_to_floppy(const string &bits);
#endif

void read_array(int subtask_id, const vector<int> &v) {
	stack<int> st; string bits = "";
	for (int i = 0; i < v.size(); ++i) {
		while (!st.empty() && v[i] > v[st.top()]) {
			st.pop(), bits += '0';
		}
		st.emplace(i), bits += '1';
	}
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int n,
        const string &bits,
        const vector<int> &a, const vector<int> &b) {
	for (int i = 0; i < LG; ++i) pre[i].assign(n, -1);
	stack<int> st;
	for (int i = 0, j = 0; i < n; ++i) {
		while (bits[j] == '0') st.pop(), ++j;
		if (!st.empty()) pre[0][i] = st.top();
		st.emplace(i), ++j;
	}

	for (int i = 1; i < LG; ++i) for (int j = 0; j < n; ++j) {
		if (pre[i - 1][j] == -1) pre[i][j] = -1;
		else pre[i][j] = pre[i - 1][pre[i - 1][j]];
	}

	vector<int> ans(a.size(), -1);
	for (int i = 0; i < a.size(); ++i) {
		int l = a[i], r = b[i];
		for (int j = LG - 1; j >= 0; --j) {
			int nxt = pre[j][r];
			if (nxt >= l) r = nxt;
		}
		ans[i] = r;
	}

	return ans;
}

#ifdef hwe
namespace Grader {
	#define NMAX 100000
	#define MMAX 100000

	int subtask_id, N, M;
	vector<int> v, sorted_v;
	vector<int> a, b;
	vector<int> correct_answers;

	// Print score to stdout and exit.
	void score_and_exit(const double pts, const char *verdict) {
	    fprintf(stderr, "%s", verdict);
	    fprintf(stdout, "%f", pts);
	    exit(0);
	}

	// Contestant sent too many bits.
	void too_many_bits() {
	    score_and_exit(0, "Too many stored bits!");
	}

	// Contestant did not send any bits.
	void misformatted_stored_bits() {
	    score_and_exit(0, "Misformatted stored bits or save_to_floppy not called!");
	}

	// Contestant did not call the answer function.
	void answer_not_provided() {
	    score_and_exit(0, "Answer not provided!");
	}

	// Contestant sent a wrong answer.
	void wrong_answer() {
	    score_and_exit(0, "Wrong answer to query!");
	}

	// Contestant sent a correct answer.
	void correct_answer() {
	    score_and_exit(1, "OK!");
	}

	void read_test() {
	    assert(scanf("%d", &subtask_id) == 1);
	    assert(scanf("%d%d", &N, &M) == 2);
	    assert(1 <= N && N <= NMAX);
	    assert(0 <= M && M <= MMAX);
	    v.resize(N);
	    for (int i = 0; i < N; ++i) {
	        assert(scanf("%d", &v[i]) == 1);
	    }

	    // Check all values are distinct.
	    sorted_v.resize(N);
	    for (int i = 0; i < N; ++i) {
	        sorted_v[i] = v[i];
	    }
	    sort(sorted_v.begin(), sorted_v.end());
	    for (int i = 0; i + 1 < N; ++i) {
	        assert(sorted_v[i] < sorted_v[i + 1]);
	    }

	    a.resize(M);
	    b.resize(M);
	    correct_answers.resize(M);
	    for (int i = 0; i < M; ++i) {
	        assert(scanf("%d%d%d", &a[i], &b[i], &correct_answers[i]) == 3);
	        assert(0 <= a[i] && a[i] <= correct_answers[i] &&
	              correct_answers[i] <= b[i] && b[i] < N);
	    }
	}

	void save_to_floppy(const string &bits) {
	    vector<int> contestant_answers = solve_queries(subtask_id, N, bits, a, b);
	    for (int i = 0; i < M; ++i) {
	        if (contestant_answers[i] != correct_answers[i]) {
	            wrong_answer();
	        }
	    }
	    correct_answer();
	    exit(0);
	}

	void test() {
	    // Read input data.
	    read_test();

	    // Send subtask_id, v.
	    read_array(subtask_id, v);
	    
	    answer_not_provided();
	}
}

void save_to_floppy(const string &bits) {
	Grader::save_to_floppy(bits);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    Grader::test();

    cerr << '\n'; return 0;
}
#endif

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72