oj.uz

Submission #401507

# Submission time Handle Problem Language Result Execution time Memory
401507 2021-05-10T12:43:53 Z nandonathaniel Floppy (RMI20_floppy) C++14
100 / 100
 131 ms 16708 KB 
#include <stdlib.h>
#include <string.h>
#include "bits/stdc++.h"
#include "floppy.h"
using namespace std;
typedef pair<int,int> pii;
const int MAXN=40005,LOG=16;

int A[MAXN],n,kiri[MAXN],kanan[MAXN],subtree[MAXN],depth[MAXN],pa[LOG][MAXN];
vector<int> adj[MAXN];
pii tree[4*MAXN];
string bits,S;

void build(int now,int L,int R){
	if(L==R){
		tree[now]={A[L],L};
		return;
	}
	int mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[now]=max(tree[2*now],tree[2*now+1]);
}

pii query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return {-1000000005,0};
	int mid=(L+R)/2;
	return max(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

void cartesian(int L,int R){
	int id=query(1,1,n,L,R).second;
	if(L<=id-1){
		bits+='1';
	}
	else{
		bits+='0';
	}
	if(id+1<=R){
		bits+='1';
	}
	else{
		bits+='0';
	}
	if(L<=id-1){
		cartesian(L,id-1);
	}
	if(id+1<=R){
		cartesian(id+1,R);
	}
}

int idx,node;

int buildtree(){
	node++;
	int hei=node;
	int cekL=idx,cekR=idx+1;
	idx+=2;
	if(S[cekL]=='1'){
		kiri[hei]=buildtree();
	}
	if(S[cekR]=='1'){
		kanan[hei]=buildtree();
	}
	return hei;
}

void dfsSz(int now){
	if(now==0)return;
	subtree[now]=1;
	dfsSz(kiri[now]);
	subtree[now]+=subtree[kiri[now]];
	dfsSz(kanan[now]);
	subtree[now]+=subtree[kanan[now]];
}

int numbering(int now,int L,int R){
	if(now==0 || L>R)return 0;
	int asli=L+subtree[kiri[now]];
	int ki=numbering(kiri[now],L,asli-1);
	if(ki){
		adj[asli].push_back(ki);
//		cout << "ze " << asli << " " << ki << '\n';
	}
	int ka=numbering(kanan[now],asli+1,R);
	if(ka){
		adj[asli].push_back(ka);
//		cout << "ze " << asli << " " << ka << '\n';
	}
	return asli;
}

void dfs(int now){
	for(auto nxt : adj[now]){
		pa[0][nxt]=now;
		for(int i=1;i<LOG;i++)pa[i][nxt]=pa[i-1][pa[i-1][nxt]];
		depth[nxt]=depth[now]+1;
		dfs(nxt);
	}
}

int LCA(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	int diff=depth[u]-depth[v];
	for(int i=LOG-1;i>=0;i--){
		if(diff & (1<<i))u=pa[i][u];
	}
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--){
		if(pa[i][u]!=pa[i][v]){
			u=pa[i][u];
			v=pa[i][v];
		}
	}
	return pa[0][u];
}

void read_array(int subtask_id, const std::vector<int> &v) {
	bits="";
    n=v.size();
    for(int i=0;i<n;i++)A[i+1]=v[i];
    build(1,1,n);
    cartesian(1,n);
    save_to_floppy(bits);
}

vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
//    cout << "gb " << bits << '\n';
    S=bits;
    idx=0;
    node=0;
    buildtree();
    dfsSz(1);
    for(int i=1;i<=N;i++){
//		cout << "chk " << subtree[i] << '\n';
	}
    int root=numbering(1,1,N);
    dfs(root);
    vector<int> answers;
    for(int i=0;i<a.size();i++){
    	answers.push_back(LCA(a[i]+1,b[i]+1)-1);
//    	cout << "jc " << answers.back() << '\n';
	}
    return answers;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:144:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
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 4 ms 2692 KB Output is correct
2 Correct 4 ms 2692 KB Output is correct
3 Correct 4 ms 2696 KB Output is correct
4 Correct 4 ms 2696 KB Output is correct
5 Correct 4 ms 2692 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5700 KB Output is correct
2 Correct 33 ms 5896 KB Output is correct
3 Correct 32 ms 6188 KB Output is correct
4 Correct 33 ms 6112 KB Output is correct
5 Correct 32 ms 5612 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 15300 KB Output is correct
2 Correct 131 ms 15100 KB Output is correct
3 Correct 125 ms 16708 KB Output is correct
4 Correct 130 ms 16524 KB Output is correct
5 Correct 128 ms 15136 KB Output is correct