제출 #467473

#제출 시각아이디문제언어결과실행 시간메모리
467473Carmel_Ab1Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
1530 ms82376 KiB
#include<bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<pl> vpl; typedef vector<ld> vld; typedef pair<ld, ld> pld; //typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; template<typename T> ostream &operator<<(ostream &os, vector<T> &a) { os << "["; for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); } os << "]\n"; return os; } #define all(x) x.begin(),x.end() #define YES out("YES") #define NO out("NO") #define out(x){cout << x << "\n"; return;} #define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL) #define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";} #define pb push_back #define umap unordered_map template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> &p) { os << "" << p.first << " " << p.second << ""; return os; } void usaco(string taskname) { string fin = taskname + ".in"; string fout = taskname + ".out"; const char *FIN = fin.c_str(); const char *FOUT = fout.c_str(); freopen(FIN, "r", stdin); freopen(FOUT, "w", stdout); } template<typename T> void read(vector<T> &v) { int n = v.size(); for (int i = 0; i < n; i++) cin >> v[i]; } template<typename T> vector<T> UNQ(vector<T> a) { vector<T> ans; for (T t:a) if (ans.empty() || t != ans.back()) ans.push_back(t); return ans; } ll ceil(ll a, ll b) { ll ans = a / b; if (a % b)ans++; return ans; } ld log(ld a, ld b) { return log(b) / log(a); } ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M ll ans = 1; while (exp) { if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M; base = ((base % M) * (base % M)) % M; exp /= 2; } return ans; } string to_base(int n, int new_base) { string s; int nn = n; while (nn) { s += to_string(nn % new_base); nn /= new_base; } reverse(all(s)); return s; } ll gcd(ll a, ll b) { if (a < b)swap(a, b); if (b == 0)return a; return gcd(b, a % b); } ll lcm(ll a, ll b) { ll x = (a / gcd(a, b)); return b * x; } vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) { if (mx == 1e18 + 1) mx = n; vl ans(n); for (int i = 0; i < n; i++) ans[i] = (mn + rand() % (mx - mn + 1)); return ans; } string substr(string s, int l, int r) { string ans; for (int i = l; i <= r; i++) ans += s[i]; return ans; } void solve(); int main() { GLHF; int t = 1; //cin >> t; while (t--) solve(); } int sz=1; int t[(1<<21)]; void update(int i,int v){ i+=sz/2; t[i]=max(t[i],v); while(i){ t[i/2]=max(t[i],t[i^1]); i/=2; } } int query(int l,int r){ int ans=0; for(l+=sz/2,r+=sz/2 +1; l<r; l/=2,r/=2){ if(l&1)ans=max(ans,t[l++]); if(r&1)ans=max(ans,t[--r]); } return ans; } void solve() { int n,q; cin >> n>> q; int a[n]; for(int i=0; i<n; i++) cin >> a[i]; while(sz<=2*n) sz*=2; for(int i=0; i<sz; i++) t[i]=0; vi qs[q]; for(int i=0; i<q; i++) qs[i].resize(4); for(int i=0; i<q; i++){ cin >> qs[i][0] >> qs[i][1] >> qs[i][2]; qs[i][0]--,qs[i][1]--; qs[i][3]=i; } for(int i=0; i<q; i++) swap(qs[i][0],qs[i][1]); sort(qs,qs+q); for(int i=0; i<q; i++) swap(qs[i][0],qs[i][1]); int ans[q]; for(int i=0; i<q; i++) ans[i]=0; int prv[n]; for(int i=0; i<n; i++) prv[i]=-1; stack<int>s; for(int i=n-1; 0<=i; i--){ while(s.size() && a[s.top()]<a[i]){ prv[s.top()]=i; s.pop(); } s.push(i); } for(int i=0,j=0; j<q && i<n; i++){ int cur=prv[i]; bool ok=1; while(cur!=-1 && ok){ if(a[cur]>a[i]) update(cur,a[cur]+a[i]); cur=prv[cur]; ok=0; } while(i<n && j<q && qs[j][1]==i){ if(query(qs[j][0],qs[j][1])<=qs[j][2]) ans[qs[j][3]]=1; j++; } } for(int i=0; i<q ;i++) cout << ans[i] << " "; }

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

sortbooks.cpp: In function 'void usaco(std::string)':
sortbooks.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FOUT, "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...