#pragma GCC optimize("O3, unroll-loops, Ofast")
#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>
#include "floppy.h"
#define pii pair<int,int>
using namespace std;
int B = 0;
int INF = numeric_limits<int>::max()/2;
struct SegmentTree{
vector<pii> S;
int len = 1;
SegmentTree(vector<int>arr){
int n = arr.size();
while(len < n) len <<= 1;
S.resize(2*len, {-INF,-1});
for(int i = 0; i < n;i++){
S[i+len] = {arr[i],i};
}
for(int i = len-1; i > 0; i--){
S[i] = max(S[i*2],S[i*2+1]);
}
}
pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return {-INF,-1};
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
}
};
void build(int l, int r, SegmentTree& seg, string& bits){
if(l == r){
bits += "00";
return;
}
pii res = seg.query(l,r+1);
if(res.second == l){
bits += "01";
build(l+1, r, seg, bits);
}else if(res.second == r){
bits += "10";
build(l, r-1, seg, bits);
}else{
bits += "11";
build(l, res.second-1, seg, bits);
build(res.second+1, r, seg, bits);
}
}
void read_array(int subtask_id, const std::vector<int> &arr) {
vector<int >v = arr;
int n =v.size();
string bits = "";
SegmentTree seg(v);
build(0,n-1,seg,bits);
cerr << bits<<endl;
save_to_floppy(bits);
}
int counter = 0;
struct Node{
int v;
int l = -1, r = -1;
int sz = 1;
int lsz = 0, rsz= 0;
};
vector<Node> cart;
void reconstruct(vector<Node>& adj, string& bits){
bool b1 = bits[counter] == '1';
bool b2 = bits[counter+1] == '1';
counter += 2;
int v = cart.size();
cart.push_back(Node{});
if(b1){
cart[v].l = cart.size();
reconstruct(adj,bits);
cart[v].sz += cart[cart[v].l].sz;
cart[v].lsz = cart[cart[v].l].sz;
}
if(b2){
cart[v].r = cart.size();
reconstruct(adj,bits);
cart[v].sz += cart[cart[v].r].sz;
cart[v].rsz = cart[cart[v].r].sz;
}
}
void buildInd(int v, int l, int r){
cart[v].v = cart[v].lsz + l;
if(cart[v].l != -1){
buildInd(cart[v].l, l, cart[v].v-1);
}
if(cart[v].r != -1){
buildInd(cart[v].r,cart[v].v+1, r);
}
}
int search(int v, int l, int r){
if(l <= cart[v].v && cart[v].v <= r){
return cart[v].v;
}
if(cart[v].v < l){
return search(cart[v].r, l, r);
}else{
return search(cart[v].l, l, r);
}
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) {
int n = N;
string bits = input;
B = ceil(log2(n));
int q = a.size();
vector<Node> adj;
reconstruct(adj,bits);
buildInd(0,0,n-1);
vector<int> answers(q);
for(int i = 0; i < q; i++){
int l, r;
l = a[i];
r = b[i];
if(l == r){
answers[i] = l;
continue;
}
answers[i] = search(0,l,r);
}
return answers;
}
컴파일 시 표준 에러 (stderr) 메시지
floppy.cpp:1:47: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("O3, unroll-loops, Ofast")
| ^
floppy.cpp:1:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
In file included from floppy.cpp:6:
floppy.h:4:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
4 | void read_array(int subtask_id, const std::vector<int> &v);
| ^
floppy.h:4:58: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:4:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:4:58: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
6 | void save_to_floppy(const std::string &bits);
| ^
floppy.h:6:44: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:6:44: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
10 | const std::vector<int> &b);
| ^
floppy.h:10:57: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
floppy.h:10:57: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:17:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
17 | SegmentTree(vector<int>arr){
| ^
floppy.cpp:17:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:31:63: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
31 | pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
| ^
floppy.cpp:31:63: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:41:56: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
41 | void build(int l, int r, SegmentTree& seg, string& bits){
| ^
floppy.cpp:41:56: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:61:60: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
61 | void read_array(int subtask_id, const std::vector<int> &arr) {
| ^
floppy.cpp:61:60: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:83:49: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
83 | void reconstruct(vector<Node>& adj, string& bits){
| ^
floppy.cpp:83:49: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:104:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
104 | void buildInd(int v, int l, int r){
| ^
floppy.cpp:104:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:115:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
115 | int search(int v, int l, int r){
| ^
floppy.cpp:115:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
floppy.cpp:127:133: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
127 | std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) {
| ^
floppy.cpp:127:133: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
