Submission #344255

#TimeUsernameProblemLanguageResultExecution timeMemory
344255RakhmandHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
34 / 100
3041 ms8556 KiB
// // A.cpp // torelax // // Created by Rakhman on 1/5/21. // #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 1e6 + 110; const long long mnn = 1e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e9 + 100; typedef long long llong; typedef unsigned long long ullong; using namespace std; int n, m, mx[mxn]; int b[mxn]; int sq = 448; vector<int> v[1010]; int main() { cin >> n >> m; for(int i = 0; i < n; i++){ cin >> b[i]; v[i / sq].push_back(b[i]); } for(int i = 0; i <= (n - 1) / sq; i++){ int kek = 0; for(int j = 0; j < v[i].size(); j++){ if(kek > v[i][j]){ mx[i] = max(mx[i], kek + v[i][j]); } kek = max(kek, v[i][j]); } sort(v[i].begin(), v[i].end()); } for(int i = 1; i <= m; i++){ int l, r, x, batkya = -1; cin >> l >> r >> x; l--, r--; int ans = 0; while(l <= r){ if(l % sq == 0 && l + sq - 1 <= r){ ans = max(ans, mx[l / sq]); int L = 0, R = v[l / sq].size() - 1; while(R - L > 1){ int m = (L + R) / 2; if(batkya >= v[l / sq][m]){ L = m; }else{ R = m; } } int lol = -1; if(batkya > v[l / sq][R]) lol = R; else if(batkya > v[l / sq][L]) lol = L; if(lol != -1) ans = max(ans, batkya + v[l / sq][lol]); batkya = max(batkya, v[l / sq][v[l / sq].size() - 1]); l += sq; }else{ if(batkya > b[l]){ ans = max(ans, batkya + b[l]); } batkya = max(batkya, b[l]); l++; } } if(ans > x){ cout << 0; }else{ cout << 1; } cout << nl; } }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j < v[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
#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...