oj.uz

Submission #922709

# Submission time Handle Problem Language Result Execution time Memory
922709 2024-02-06T03:43:17 Z vjudge1 Floppy (RMI20_floppy) C++17
100 / 100
 72 ms 17976 KB 
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 4e4, LOG = 15;

int N, a[NM+5];
int f[LOG+5][NM+5];
string s;
int ptr = 0, d[NM+5], sz[NM+5];

void build_sparse(){
	for (int i = 1; i <= N; i++) f[0][i] = i;
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= N; j++){
			int x = f[i-1][j], y = f[i-1][j+(1<<(i-1))];
			if (a[x] > a[y]) f[i][j] = x; else f[i][j] = y;
		}
}

int get(int l, int r){
	int i = __lg(r-l+1), x = f[i][l], y = f[i][r-(1<<i)+1];
	if (a[x] > a[y]) return x;
	return y;
}

void dnc(int l, int r){
	if (l > r) return;
	if (l == r){
		s.push_back('0');
		s.push_back('0');
		return;
	}
	int mid = get(l, r);
	if (mid > l) s.push_back('1'); else s.push_back('0');
	if (mid < r) s.push_back('1'); else s.push_back('0');
	dnc(l, mid-1);
	dnc(mid+1, r);
}

void read_array(int subtask_id, const vector<int> &v) {
    N = isz(v);
    for (int i = 1; i <= N; i++) a[i] = v[i-1];
    build_sparse();
    dnc(1, N);
    save_to_floppy(s);
}

void dfs(int u){
	sz[u] = 1;
	d[u] = 0;
	if (s[2*u] == '1'){
		ptr += 2;
		int v = ptr/2;
		dfs(v);
		sz[u] += sz[v];
		d[u] = max(d[u], d[v]+1);
	}
	if (s[2*u+1] == '1'){
		ptr += 2;
		int v = ptr/2;
		dfs(v);
		sz[u] += sz[v];
		d[u] = max(d[u], d[v]+1);
	}
}

void restore(int u, int l, int r){
	int mid = (s[ptr] == '1' ? l+sz[u+1] : l);
	a[mid] = d[u];
	
	if (s[2*u] == '1'){
		ptr += 2;
		restore(ptr/2, l, mid-1);
	}
	if (s[2*u+1] == '1'){
		ptr += 2;
		restore(ptr/2, mid+1, r);
	}
}

vector<int> solve_queries(int subtask_id, int _N, const string &bits, const vector<int> &l, const vector<int> &r) {
    s = bits;
    N = _N;
    dfs(0);
    ptr = 0;
    restore(0, 1, N);
    build_sparse();
    
    vector <int> ans(isz(l));
    for (int i = 0; i < isz(l); i++){
    	ans[i] = get(l[i]+1, r[i]+1)-1;
	}
	
	return ans;
}

Compilation message

stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4916 KB Output is correct
2 Correct 2 ms 5016 KB Output is correct
3 Correct 2 ms 4912 KB Output is correct
4 Correct 2 ms 4928 KB Output is correct
5 Correct 2 ms 4928 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7468 KB Output is correct
2 Correct 16 ms 7592 KB Output is correct
3 Correct 17 ms 7992 KB Output is correct
4 Correct 18 ms 7872 KB Output is correct
5 Correct 16 ms 7608 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16700 KB Output is correct
2 Correct 67 ms 16912 KB Output is correct
3 Correct 72 ms 17976 KB Output is correct
4 Correct 65 ms 17716 KB Output is correct
5 Correct 65 ms 16900 KB Output is correct