Submission #56810

#TimeUsernameProblemLanguageResultExecution timeMemory
56810polyfishDojave (COCI17_dojave)C++14
126 / 140
890 ms126304 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int MAX_N = 1100002; struct query { int l, r, val; query() {} query(int l, int r, int val): l(l), r(r), val(val) {} bool operator<(const query & Q) { return val<Q.val; } }; struct fenwick_tree { vector<int> bit; int n; void init(int _n) { n = _n; bit.resize(n+1, 0); } void upd(int id) { for (; id<=n; id += id & (-id)) ++bit[id]; } int get(int id) { if (id==0) return 0; int res = 0; for (; id>0; id -= id & (-id)) res += bit[id]; return res; } int get(int l, int r) { if (l>r) return 0; return get(r) - get(l-1); } }; int m, n, a[MAX_N], pos[MAX_N], L[MAX_N], R[MAX_N]; vector<pair<int, int> > seg; vector<query> q; void enter() { cin >> m; n = 1 << m; for (int i=0; i<n; ++i) cin >> a[i]; } void init() { // debug(n); for (int i=0; i<n; ++i) pos[a[i]] = i; for (int i=0; i<n; ++i) { if (pos[(n-1)^a[i]]<i) seg.push_back(make_pair(pos[(n-1)^a[i]], i)); } // for (int i=0; i<seg.size(); ++i) // cerr << seg[i].first << ' ' << seg[i].second << '\n'; } void make_L() { sort(seg.begin(), seg.end()); int head = -1; priority_queue<int, vector<int>, greater<int> > pq; for (int i=0; i<n; ++i) { while (head+1<seg.size() && seg[head+1].first<i) { ++head; pq.push(seg[head].second); } int x = n; while (pq.size()) { int tmp = pq.top(); if (tmp>=i) { x = tmp; break; } pq.pop(); } // debug(x); L[i] = x - 1; } //PR0(L, n); } void make_R() { sort(seg.begin(), seg.end(), [](pair<int, int> a, pair<int, int> b) { return a.second>b.second; }); int head = -1; priority_queue<int> pq; for (int i=n-1; i>=0; --i) { while (head+1<seg.size() && seg[head+1].second>i) { ++head; pq.push(seg[head].first); } int x = -1; while (pq.size()) { int tmp = pq.top(); if (tmp<=i) { x = tmp; break; } pq.pop(); } R[i] = x+1; } //PR0(R, n); } void make_query() { for (int i=0; i<n; ++i) { q.push_back(query(i, L[i], i)); } sort(q.begin(), q.end()); // for (int i=0; i<q.size(); ++i) // cerr << q[i].l << ' ' << q[i].r << ' ' << q[i].val << '\n'; } int64_t solve_query() { vector<pair<int, int> > b; fenwick_tree tr[4]; for (int i=0; i<4; ++i) tr[i].init(n); int64_t res = 0; for (int i=0; i<n; ++i) b.push_back(make_pair(R[i], i)); sort(b.begin(), b.end()); int head = -1; for (int i=0; i<q.size(); ++i) { int l = q[i].l, r = q[i].r, val = q[i].val; while (head+1<b.size() && b[head+1].first<=val) { ++head; // if (l==0) // debug((b[head].second+1)%4); tr[(b[head].second+1)%4].upd(b[head].second + 1); } res += tr[l%4].get(l+1, r+1); } return 1LL * n * (n + 1) / 2 - res; } int main() { //#define OFFLINE_JUDGE doraemon #ifdef OFFLINE_JUDGE freopen(FILE_NAME".inp", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); init(); make_L(); make_R(); make_query(); cout << solve_query(); }

Compilation message (stderr)

dojave.cpp: In function 'void make_L()':
dojave.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<seg.size() && seg[head+1].first<i) {
          ~~~~~~^~~~~~~~~~~
dojave.cpp: In function 'void make_R()':
dojave.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<seg.size() && seg[head+1].second>i) {
          ~~~~~~^~~~~~~~~~~
dojave.cpp: In function 'int64_t solve_query()':
dojave.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q.size(); ++i) {
                ~^~~~~~~~~
dojave.cpp:149:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (head+1<b.size() && b[head+1].first<=val) {
          ~~~~~~^~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...