Submission #1094249

#TimeUsernameProblemLanguageResultExecution timeMemory
1094249cpptowinHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
2474 ms262144 KiB
#include <bits/stdc++.h> #define fo(i, d, c) for (int i = d; i <= c; i++) #define fod(i, c, d) for (int i = c; i >= d; i--) #define maxn 1000010 #define N 1010 #define fi first #define se second #define pb emplace_back #define en cout << "\n"; #define int long long #define inf (int)1e18 #define bitcount(x) __builtin_popcountll(x) #define pii pair<int, int> #define vii vector<pii> #define lb(x) x & -x #define bit(i, j) ((i >> j) & 1) #define offbit(i, j) (i ^ (1LL << j)) #define onbit(i, j) (i | (1LL << j)) #define vi vector<int> #define all(x) x.begin(), x.end() #define ss(x) (int)x.size() template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } using namespace std; const int nsqrt = 450; const int mod = 1e9 + 7; void add(int &x, int k) { x += k; x %= mod; if(x < 0) x += mod; } void del(int &x, int k) { x -= k; x %= mod; if(x < 0) x += mod; } const int MAXN = 8000005; // n*(log(max(ai))+4) namespace WaveletTree { // nenso -> build -> query int n; int arr[maxn], w[MAXN], nxt = 1, in = 0; int lc[MAXN], rc[MAXN], l[MAXN], r[MAXN]; int b[MAXN]; const int from = 0, to = maxn; vi nen; void nenso() { fo(i, 1, n) nen.pb(arr[i]); sort(all(nen)); nen.erase(unique(all(nen)), nen.end()); fo(i, 1, n) arr[i] = lower_bound(all(nen), arr[i]) - nen.begin(); } void build(int psz = -1, bool f = 1, int pnd = -1, int nd = 1, int s = from, int e = to) { l[nd] = ++in, r[nd] = in - 1; int midp = psz >> 1, mid = (s + e) >> 1, i1 = (nd == 1) ? n : r[pnd]; for (int i = (nd == 1) ? 1 : l[pnd]; i <= i1; i++) if (nd == 1 || (f && w[i] <= midp) || (!f && w[i] > midp)) w[in] = (nd == 1) ? arr[i] : w[i], r[nd] = in, b[in] = b[in - 1] + (w[in] <= mid), in++; if (s == e) return; int sz = (nd == 1) ? n : r[nd] - l[nd] + 1; if (b[r[nd]] - b[l[nd] - 1]) lc[nd] = ++nxt, build(s + e, 1, nd, lc[nd], s, mid); if (b[r[nd]] - b[l[nd] - 1] != sz) rc[nd] = ++nxt, build(s + e, 0, nd, rc[nd], mid + 1, e); } /* note: - w stores the array elements of each node - b stores the prefix sum of frequency of elements <= mid of each node - lc contains the node number of the left child of a node - rc contains the node number of the right child of a node - nxt is used to find the new node number to assign to a node - in is used to allot space in the w array for each node - [l[nd],r[nd]] is the range for elements of node nd in w and b - psz is the number of elements in the parent of a node - pnd is the parent of a node - f is 1 if the current node is a left child, 0 otherwise */ // kth smallest element in range [l1,r1] int kth(int l1, int r1, int k, int nd = 1, int s = from, int e = to) { if (s == e) return s; int mid = (s + e) >> 1; int got = b[l[nd] + r1] - b[l[nd] + l1 - 1]; if (got >= k) return kth(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid); return kth(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k - got, rc[nd], mid + 1, e); } int KTH(int l,int r,int k) { return nen[kth(l,r,k)]; } // count of k in range [l1,r1] int count(int l1, int r1, int k, int nd = 1, int s = from, int e = to) { if (s == e) return b[l[nd] + r1] - b[l[nd] + l1 - 1]; int mid = (s + e) >> 1; if (mid >= k) return count(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid); return count(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e); } int COUNT(int l,int r,int k) { k = lower_bound(all(nen),k) - nen.begin() + 1; return count(l,r,k); } // count of numbers <= to k in range [l1,r1] int lte(int l1, int r1, int k, int nd = 1, int s = from, int e = to) { if (l1 > r1 || k < s) return 0; if (e <= k) return r1 - l1 + 1; int mid = (s + e) >> 1; return lte(b[l[nd] + l1 - 1], b[l[nd] + r1] - 1, k, lc[nd], s, mid) + lte(l1 - b[l[nd] + l1 - 1], r1 - b[l[nd] + r1], k, rc[nd], mid + 1, e); } int LTE(int l,int r,int k) { k = upper_bound(all(nen),k) - nen.begin() - 1; return lte(l,r,k); } } struct BIT { int t[maxn]; void up(int x,int val) { for( ; x < maxn ; x += lb(x)) maximize(t[x],val); } void clear(int x) { for( ; x < maxn ; x += lb(x)) t[x] = 0; } int get(int x) { int ans = 0; for( ; x ; x -= lb(x)) maximize(ans,t[x]); return ans; } }minn; struct BIT1 { int t[maxn]; void up(int x,int val) { for( ; x ; x -= lb(x)) maximize(t[x],val); } void clear(int x) { for( ; x ; x -= lb(x)) t[x] = 0; } int get(int x) { int ans = 0; for( ; x < maxn ; x += lb(x)) maximize(ans,t[x]); return ans; } }maxx; int n,q,a[maxn]; int res[maxn]; int suml[maxn],sumr[maxn]; int maxl[maxn]; vi nen; void calc(int l,int r,vector<array<int,4>> qry) { int mid = l + r >> 1; fod(i,mid,l) { maxl[i] = max(maxl[i + 1],a[i]); int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1; suml[i] = minn.get(lb) + a[i]; maximize(suml[i],suml[i + 1]); minn.up(lb,a[i]); } fo(i,mid + 1,r) { int lb = lower_bound(all(nen),a[i]) - nen.begin() + 1; sumr[i] = maxx.get(lb) + a[i]; maximize(sumr[i],sumr[i - 1]); maxx.up(lb,a[i]); } vector<array<int,4>> ll,rr; for(auto [l,r,val,id] : qry) { if(l <= mid and r >= mid) { int maxx = max(suml[l],sumr[r]); if(maxx > val) res[id] = 1; else { int L = max(val - maxl[l],0ll); if(WaveletTree::lte(mid,r - 1,maxl[l]) - WaveletTree::lte(mid,r - 1,L) > 0) res[id] = 1; } } else if(r < mid) ll.push_back({l,r,val,id}); else if(l > mid) rr.push_back({l,r,val,id}); } if(l != r) { calc(l,mid,ll); calc(mid + 1,r,rr); } } main() { #define name "TASK" if (fopen(name ".inp", "r")) { freopen(name ".inp", "r", stdin); freopen(name ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; WaveletTree::n = n; fo(i,1,n) { cin >> a[i]; nen.pb(a[i]); WaveletTree::arr[i] = a[i]; } sort(all(nen)); nen.erase(unique(all(nen)),nen.end()); WaveletTree::build(); vector<array<int,4>> qry(q); // cout << WaveletTree::lte(0,4,8);en; fo(i,0,q - 1) { cin >> qry[i][0] >> qry[i][1] >> qry[i][2]; qry[i][3] = i + 1; } calc(1,n,qry); fo(i,1,q) cout << (res[i] ^ 1) << "\n"; }

Compilation message (stderr)

sortbooks.cpp: In function 'void calc(long long int, long long int, std::vector<std::array<long long int, 4> >)':
sortbooks.cpp:196:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  196 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:235:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  235 | main()
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:240:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen(name ".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...