| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 574877 |
2022-06-09T12:42:53 Z |
urosk |
Floppy (RMI20_floppy) |
C++14 |
|
1000 ms |
66148 KB |
#include "floppy.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define llinf 1000000005 // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
#define maxn 1000005
#define lg 25
ll n;
ll A[maxn];
ll t[4*maxn];
void init(ll v,ll tl,ll tr){
if(tl==tr){
t[v] = A[tl];
return;
}
ll mid = (tl+tr)/2;
init(2*v,tl,mid);
init(2*v+1,mid+1,tr);
t[v] = max(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
if(l>r) return 0;
if(tl==l&&tr==r) return t[v];
ll mid = (tl+tr)/2;
return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
map<ll,ll> mp;
ll lf[maxn];
ll rf[maxn];
ll tr = 1;
void construct(ll node,ll l,ll r){
ll i = mp[get(1,1,n,l,r)];
if(node>maxn-1){
while(1){
here;
}
}
if(l>r) return;
if(l==r) return;
lf[node] = 1;
rf[node] = 1;
if(l==i) lf[node] = 0;
if(r==i) rf[node] = 0;
if(lf[node]){tr++; construct(tr,l,i-1);}
if(rf[node]){tr++; construct(tr,i+1,r);}
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = sz(v);
for(ll i = 1;i<=n;i++) A[i] = v[i-1];
for(ll i = 1;i<=n;i++) mp[A[i]] = i;
init(1,1,n);
string s;
construct(1,1,n);
for(ll i = 1;i<=n;i++){
if(lf[i]) s.pb('1');
else s.pb('0');
if(rf[i]) s.pb('1');
else s.pb('0');
}
save_to_floppy(s);
}
ll dp[maxn];
ll inv[maxn];
vector<ll> g[maxn];
ll st[maxn][lg];
ll it = 1;
ll in[maxn];
ll id[maxn];
ll out[maxn];
ll tim = 1;
ll f = 1;
ll x = 2;
void dfs(ll i,ll par){
in[i] = tim++;
st[i][0] = par;
lf[i] = A[2*i-1];
rf[i] = A[2*i];
if(lf[i]!=0) lf[i] = x++;
if(lf[i]!=0){
dfs(lf[i],i);
}
id[f++] = i;
inv[i] = f-1;
if(rf[i]!=0) rf[i] = x++;
if(rf[i]!=0){
dfs(rf[i],i);
}
out[i] = tim - 1;
}
bool intree(ll x,ll y){return in[x]>=in[y]&&out[x]<=out[y];}
ll lca(ll x,ll y){
if(intree(x,y)) return y;
if(intree(y,x)) return x;
for(ll j = lg-1;j>=0;j--){
if(!intree(x,st[y][j])) y = st[y][j];
}
return st[y][0];
}
std::vector<int> solve_queries(int subtask_id, int N,const std::string &bits,const std::vector<int> &a, const std::vector<int> &b) {
n = N;
for(ll i = 1;i<=2*n;i++) A[i] = (bits[i-1]-'0');
dfs(1,1);
for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
vector<ll> ans;
for(ll i = 0;i<sz(a);i++){
ll l = a[i]+1;
ll r = b[i]+1;
ans.pb(inv[lca(id[l],id[r])]-1);
}
return ans;
}
/*
3
4 10
40 20 30 10
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3
*/
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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
47896 KB |
Output is correct |
| 2 |
Correct |
28 ms |
47716 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47972 KB |
Output is correct |
| 4 |
Correct |
28 ms |
47860 KB |
Output is correct |
| 5 |
Correct |
28 ms |
47952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
66148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
58896 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
