Submission #737221

#TimeUsernameProblemLanguageResultExecution timeMemory
737221OlympiaZoltan (COCI16_zoltan)C++17
91 / 140
722 ms40296 KiB
#include <iostream> #include <set> #include <cmath> #include <queue> #include <vector> #include <cstdlib> #include <ctime> #include <cmath> #include <algorithm> #include <cassert> #include <map> #include <deque> using namespace std; const int MOD = 1e9 + 7; struct Node { int mx = 0; int64_t cnt = 0; Node (int mx, int cnt) { this->mx = mx, this->cnt = cnt; } }; struct SegmentTree { vector<Node> vec; Node id = Node(-1, 1); Node merge (Node left, Node right) { if (left.mx == -1) return right; if (right.mx == -1) return left; if (left.mx > right.mx) return left; if (left.mx < right.mx) return right; left.cnt += right.cnt; left.cnt %= MOD; return left; } Node query (int dum, int tl, int tr, int l, int r) { if (tl >= l and tr <= r) { return vec[dum]; } if (r < tl or tr < l) { return id; } return merge(query(2 * dum + 1, tl, (tl + tr)/2, l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r)); } Node query (int l, int r) { return query(0, 0, (int)vec.size()/2 - 1, l, r); } void update (int dum, Node node) { dum += (int)vec.size()/2 - 1; vec[dum] = node; while (dum != 0) { dum = (dum - 1)/2; vec[dum] = merge(vec[2 * dum + 1], vec[2 * dum + 2]); } } SegmentTree (int n) { n = (1 << (int)log2(n)) * 2; vec.assign(2 * n, id); } }; SegmentTree st = SegmentTree(1); vector<Node> lis (vector<int>& v) { st.vec.assign(st.vec.size(), st.id); map<int,vector<int>> oc; for (int i = 0; i < v.size(); i++) { oc[-v[i]].push_back(i); } vector<Node> vec; vec.push_back(Node(0, 1)); int used = pow(2, v.size() - 1); for (auto& p: oc) { vector<Node> upd; for (int i: p.second) { Node node = st.query(i + 1, (int)v.size() - 1); if (node.mx == -1) { node = Node(1, 1); } else { node.mx += 1; } upd.push_back(node); } reverse(upd.begin(), upd.end()); for (int i: p.second) { st.update(i, upd.back()), upd.pop_back(); } Node g = st.id; for (int i: p.second) { g = st.merge(g, st.query(i, i)); } vec.emplace_back(g); } return vec; } vector<Node> lds (vector<int>& v) { st.vec.assign(st.vec.size(), st.id); map<int,vector<int>> oc; for (int i = 0; i < v.size(); i++) { oc[v[i]].push_back(i); } vector<Node> vec; vec.push_back(Node(0, 1)); for (auto& p: oc) { vector<Node> upd; for (int i: p.second) { Node node = st.query(i + 1, (int)v.size() - 1); if (node.mx == -1) { node = Node(1, 1); } else { node.mx += 1; } upd.push_back(node); } reverse(upd.begin(), upd.end()); for (int i: p.second) { st.update(i, upd.back()), upd.pop_back(); } vec.emplace_back(st.query(0, (int)v.size() - 1)); } reverse(vec.begin(), vec.end()); return vec; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; st = SegmentTree(n); vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } auto a1 = lds(v); auto a2 = lis(v); int64_t mx = 0, cnt = 0; for (int i = 0; i < a1.size(); i++) { if (a1[i].mx + a2[i].mx > mx) { mx = a1[i].mx + a2[i].mx; cnt = (a1[i].cnt * a2[i].cnt) % MOD; cnt %= MOD; } else if (a1[i].mx + a2[i].mx == mx) { cnt += (a1[i].cnt * a2[i].cnt) % MOD; cnt %= MOD; } } for (int i = 0; i < n - mx; i++) { cnt *= 2; cnt %= MOD; } if (cnt % 2 == 0) cnt /= 2; else cnt = (cnt + MOD)/2 % MOD; cout << mx << " " << cnt; }

Compilation message (stderr)

zoltan.cpp: In function 'std::vector<Node> lis(std::vector<int>&)':
zoltan.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:68:9: warning: unused variable 'used' [-Wunused-variable]
   68 |     int used = pow(2, v.size() - 1);
      |         ^~~~
zoltan.cpp: In function 'std::vector<Node> lds(std::vector<int>&)':
zoltan.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < a1.size(); i++) {
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...