oj.uz

Submission #538203

# Submission time Handle Problem Language Result Execution time Memory
538203 2022-03-16T09:00:53 Z AdamGS Floppy (RMI20_floppy) C++17
100 / 100
 111 ms 14076 KB 
#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e4+7;
pair<int,int>tr[4*LIM], G[LIM];
string s;
int ile[LIM], n, post, akt;
int cnt(int l, int r) {
  l+=n; r+=n;
  pair<int,int>ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans.nd;
}
void koduj(int l, int r) {
  int x=cnt(l, r);
  if(x!=l) s+="1"; else s+="0";
  if(x!=r) s+="1"; else s+="0";
  if(x!=l) koduj(l, x-1);
  if(x!=r) koduj(x+1, r);
}
void odkoduj(int o) {
  int x=akt;
  ++akt;
  if(o!=-1) G[o].nd=x;
  if(s[2*x]=='1') {
    G[x].st=akt;
    odkoduj(-1);
  }
  if(s[2*x+1]=='1') odkoduj(x);
}
void DFS(int x, int v) {
  if(G[x].st!=-1) DFS(G[x].st, v+1);
  ++akt;
  tr[n+akt-1]={-v+1000000, akt-1};
  if(G[x].nd!=-1) DFS(G[x].nd, v+1);
}
void read_array(int subtask_id, const vector<int> &V) {
  n=1;
  while(n<V.size()) n*=2;
  rep(i, V.size()) tr[n+i]={V[i], i};
  for(int i=n-1; i; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  s="";
  koduj(0, V.size()-1);
  save_to_floppy(s);
}
vector<int>solve_queries(int subtask_id, int N, const string &V, 
    const vector<int>&A, const vector<int>&B) {
  rep(i, N) G[i]={-1, -1};
  s=V;
  n=1;
  while(n<N) n*=2;
  odkoduj(-1);
  akt=0;
  DFS(0, 0);
  for(int i=n-1; i; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  vector<int>ans;
  rep(i, A.size()) ans.pb(cnt(A[i], B[i]));
  return ans;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:49:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while(n<V.size()) n*=2;
      |         ~^~~~~~~~~
floppy.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
floppy.cpp:50:3: note: in expansion of macro 'rep'
   50 |   rep(i, V.size()) tr[n+i]={V[i], i};
      |   ^~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
floppy.cpp:67:3: note: in expansion of macro 'rep'
   67 |   rep(i, A.size()) ans.pb(cnt(A[i], B[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 3 ms 780 KB Output is correct
2 Correct 2 ms 796 KB Output is correct
3 Correct 3 ms 804 KB Output is correct
4 Correct 2 ms 796 KB Output is correct
5 Correct 2 ms 808 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2980 KB Output is correct
2 Correct 30 ms 3808 KB Output is correct
3 Correct 23 ms 3728 KB Output is correct
4 Correct 25 ms 3848 KB Output is correct
5 Correct 27 ms 3640 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9992 KB Output is correct
2 Correct 97 ms 13472 KB Output is correct
3 Correct 91 ms 13472 KB Output is correct
4 Correct 111 ms 14076 KB Output is correct
5 Correct 90 ms 13552 KB Output is correct