제출 #377234

#제출 시각아이디문제언어결과실행 시간메모리
377234ntabc05101Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
34 / 100
821 ms128748 KiB
#ifndef LOCAL #define NDEBUG 1 #endif // LOCAL #include<bits/stdc++.h> #define taskname "" #define f first #define s second const int max_n=100000; int nodes[max_n<<2]; int L[max_n<<2], H[max_n<<2]; void buildRange(int node, int low, int high) { L[node]=low, H[node]=high; if (low==high) { return ; } int mid=low+high>>1; buildRange(node<<1, low, mid); buildRange(node<<1|1, mid+1, high); } void update(int node, int posq, int value) { if (L[node]==H[node]) { nodes[node]=std::max(nodes[node], value); return ; } if (posq>H[node<<1]) { update(node<<1|1, posq, value); } else { update(node<<1, posq, value); } nodes[node]=std::max(nodes[node<<1], nodes[node<<1|1]); } int get(int node, int leftq, int rightq) { if (leftq>H[node] or rightq<L[node]) { return 0; } if (leftq<=L[node] and rightq>=H[node]) { return nodes[node]; } return std::max(get(node<<1, leftq, rightq), get(node<<1|1, leftq, rightq)); } int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } else if (fopen(taskname".in", "r")) { freopen(taskname".in", "r", stdin); freopen(taskname".out", "w", stdout); } std::ios_base::sync_with_stdio(0); std::cin.tie(0); int n, m; std::cin>>n>>m; int w[n]; for (int i=0; i<n; ++i) { std::cin>>w[i]; } std::vector< std::pair< std::pair<int, int>, int > > q[n]; for (int i=0; i<m; ++i) { int left, right, k; std::cin>>left>>right>>k; --left, --right; q[right].push_back({{left, k}, i}); } bool result[m]; buildRange(1, 0, n-1); std::deque<int> deq; for (int i=0; i<n; ++i) { while (!deq.empty() and w[deq.back()]<=w[i]) { deq.pop_back(); } if (!deq.empty()) { update(1, deq.back(), w[deq.back()]+w[i]); } deq.push_back(i); for (auto& Q: q[i]) { result[Q.s]=(get(1, Q.f.f, i)<=Q.f.s); } } for (int i=0; i<m; ++i) { std::cout<<result[i]<<"\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'void buildRange(int, int, int)':
sortbooks.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid=low+high>>1;
      |                 ~~~^~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |                 freopen(taskname".in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...