Submission #1078898

#TimeUsernameProblemLanguageResultExecution timeMemory
1078898quangminh412Stone Arranging 2 (JOI23_ho_t1)C++14
25 / 100
33 ms40544 KiB
#include <bits/stdc++.h> using namespace std; /* John Watson https://codeforces.com/profile/quangminh98 Mua Code nhu mua Florentino !! */ #define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long const int maxn = 2e5 + 9; const int segsize = 4 * maxn; int n; int arr[maxn]; class SegmentTree { struct Node { int sum; int lazy; Node(int sum = 0, int lazy = -1) : sum(sum), lazy(lazy) {} Node operator + (const Node& other) { Node res; res.sum = sum + other.sum; res.lazy = -1; return res; } }; vector<Node> st; int n; void pass(int head, int l, int r) { if (st[head].lazy == -1 || l == r) return; int mid = l + r >> 1; st[2 * head].sum = (mid - l + 1) * st[head].lazy; st[2 * head + 1].sum = (r - mid) * st[head].lazy; st[2 * head].lazy = st[head].lazy; st[2 * head + 1].lazy = st[head].lazy; st[head].lazy = -1; } void update(int head, int l, int r, int u, int v, int val) { pass(head, l, r); if (l > v || r < u) return; if (u <= l && r <= v) { st[head].sum = (r - l + 1) * val; st[head].lazy = val; return; } int mid = l + r >> 1; update(2 * head, l, mid, u, v, val); update(2 * head + 1, mid + 1, r, u, v, val); st[head] = st[2 * head] + st[2 * head + 1]; } int query(int head, int l, int r, int u, int v) { if (u > v) return -1; pass(head, l, r); if (l > v || r < u) return -1; int mid = l + r >> 1; int q1 = -1, q2 = -1; if (st[2 * head + 1].sum > 0) { q2 = query(2 * head + 1, mid + 1, r, u, v); if (q2 == -1) q1 = query(2 * head, l, mid, u, v); } else q1 = query(2 * head, l, mid, u, v); return max(q1, q2); } int getpos(int head, int l, int r, int pos) { if (l == r) return st[head].sum; int mid = l + r >> 1; if (pos <= mid) return getpos(2 * head, l, mid, pos); return getpos(2 * head + 1, mid + 1, r, pos); } public: SegmentTree(int n = 0) : n(n) { st.resize(segsize, Node(0, -1)); } void update(int u, int v, int val) { update(1, 1, n, u, v, val); } int query(int u, int v) { return query(1, 1, n, u, v); } int getpos(int pos) { return getpos(1, 1, n, pos); } }; void solve_2() { SegmentTree seg[3]; for (int i = 1; i < 3; i++) seg[i] = SegmentTree(n); for (int i = 1; i <= n; i++) { int pos = seg[arr[i]].query(1, i - 1); if (pos != -1) { seg[arr[i]].update(pos, i - 1, 1); seg[3 - arr[i]].update(pos, i - 1, 0); } seg[arr[i]].update(i, i, 1); } for (int i = 1; i <= n; i++) { int pos1 = seg[1].getpos(i); int pos2 = seg[2].getpos(i); cout << (pos1 == 1 ? 1 : 2) << '\n'; } } void solve_1() { for (int i = 1; i <= n; i++) { int mx = -1; for (int j = 1; j < i; j++) if (arr[j] == arr[i]) mx = max(mx, j); if (mx != -1) for (int j = mx; j < i; j++) arr[j] = arr[i]; } for (int i = 1; i <= n; i++) cout << arr[i] << '\n'; } signed main() { if (fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } faster(); cin >> n; bool sub2 = true; for (int i = 1; i <= n; i++) { cin >> arr[i]; if (arr[i] > 2) sub2 = false; } if (n <= 2000) { solve_1(); return 0; } if (sub2 == true) { solve_2(); return 0; } return 0; }

Compilation message (stderr)

Main.cpp: In member function 'void SegmentTree::pass(int, int, int)':
Main.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
Main.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
Main.cpp:78:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'int SegmentTree::getpos(int, int, int, int)':
Main.cpp:97:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void solve_2()':
Main.cpp:131:7: warning: unused variable 'pos2' [-Wunused-variable]
  131 |   int pos2 = seg[2].getpos(i);
      |       ^~~~
Main.cpp: In function 'int main()':
Main.cpp:157:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:158:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...