제출 #286338

#제출 시각아이디문제언어결과실행 시간메모리
286338SomeoneUnknownHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
2487 ms262148 KiB
#include <bits/stdc++.h> using namespace std; vector<int> bks; struct node{ int lo, hi, mid, heaviestswap; vector<int> svals; node *lft, *rght; node(int l, int h){ lo = l; hi = h; mid = (l+h)/2; if(l == h){ heaviestswap = 0; svals.push_back(bks[l]); }else{ lft = new node(l, mid); rght = new node(mid+1, h); heaviestswap = max(lft->heaviestswap, rght->heaviestswap); bool hstbd = true; int lmax = lft->svals.back(); if(lmax > rght->svals.back()){ hstbd = false; heaviestswap = max(heaviestswap, lft->svals.back()+rght->svals.back()); }//*/ int lp = 0; int rp = 0; lft->svals.push_back(1000000009); rght->svals.push_back(1000000009); while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){ if(hstbd && rght->svals[rp] >= lmax){ hstbd = false; if(rp != 0){ heaviestswap = max(heaviestswap, lmax+rght->svals[rp-1]); } } if(lft->svals[lp] > rght->svals[rp]){ svals.push_back(rght->svals[rp]); ++rp; }else{ svals.push_back(lft->svals[lp]); ++lp; } } lft->svals.pop_back(); rght->svals.pop_back(); } } int ghs(int l, int h){ //Get heaviest swap if(l <= lo && hi <= h){ return heaviestswap; } //int rmin = mex; int lmax = -1000000009; int res = 0; if(l <= mid){ res = max(res, lft->ghs(l,h)); lmax = lft->glnstx(l,h,1000000009); } if(mid < h){ res = max(res, rght->ghs(l,h)); res = max(res, lmax+rght->glnstx(l,h,lmax)); } return res; } int glnstx(int l, int h, int x){ //get largest number smaller than x if(l <= lo && hi <= h){ if(x == 1000000009) return svals.back(); int l1 = -1; int h1 = svals.size(); while(h1-l1 > 1){ int m1 = (h1+l1)/2; if(svals[m1] < x){ l1 = m1; }else{ h1 = m1; } } if(l1 == -1) return -1000000009; return svals[l1]; } //int rmin = mex; int best = -1000000009; if(mid < h){ best = max(best, rght->glnstx(l, h, x)); } if(l <= mid){ best = max(best, lft->glnstx(l, h, x)); } return best; } } *root; int main(){ int n, q; scanf("%d %d", &n, &q); bks.push_back(0); for(int i = 0; i < n; ++i){ int x; scanf("%d", &x); bks.push_back(x); } root = new node(1, n); if(n > 200005) return 0; for(int i = 0; i < q; ++i){ int l, r, w; scanf("%d %d %d", &l, &r, &w); if(root->ghs(l,r) > w){ printf("0\n"); }else{ printf("1\n"); } } }

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

sortbooks.cpp: In constructor 'node::node(int, int)':
sortbooks.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:31:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
sortbooks.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%d %d %d", &l, &r, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...