oj.uz

Submission #603642

# Submission time Handle Problem Language Result Execution time Memory
603642 2022-07-24T09:17:07 Z CSQ31 Floppy (RMI20_floppy) C++17
28 / 100
 56 ms 6696 KB 
#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;

void read_array(int subtask_id, const vector<int> &v) {
	int n = v.size();
	vector<array<int,2>>u(n);
	for(int i=0;i<n;i++)u[i] = {v[i],i};
	sort(u.begin(),u.end());
	vector<int>pos(n);
	for(int i=0;i<n;i++)pos[u[i][1]] = i;
	string bits;
	for(int i=0;i<n;i++){
		for(int j=0;j<14;j++){
			if(pos[i]&(1<<j))bits+="1";
			else bits+="0";
			
		}
	}
	
    save_to_floppy(bits);
}
array<int,2>T[100000],t[1000000];
void build(int v,int l,int r){
	if(l==r){
		t[v] = T[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	t[v] = max(t[2*v],t[2*v+1]);
	
}
array<int,2>query(int v,int l,int r,int tl,int tr){
	if(l>r)return {-1,-1};
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	return max(query(2*v,l,min(tm,r),tl,tm),
	           query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
vector<int> solve_queries(int subtask_id, int n,const string &bits,const vector<int> &a, const std::vector<int> &b) {
	int c = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<14;j++){
			if(bits[c] == '1')T[i][0]+=(1<<j);
			c++;
		}
		T[i][1] = i;
	}
	build(1,0,n-1);
	int q = a.size();
    vector<int> answers(q);
    for(int i=0;i<q;i++){
		answers[i] = query(1,a[i],b[i],0,n-1)[1];
	}

    return answers;
}

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 804 KB Output is correct
2 Correct 3 ms 788 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 3 ms 808 KB Output is correct
5 Correct 3 ms 804 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4292 KB Output is correct
2 Correct 39 ms 4280 KB Output is correct
3 Correct 47 ms 4180 KB Output is correct
4 Correct 56 ms 4264 KB Output is correct
5 Correct 40 ms 4300 KB Output is correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 6696 KB L is too large
2 Halted 0 ms 0 KB -