Submission #522194

#TimeUsernameProblemLanguageResultExecution timeMemory
522194Killer2501Simple game (IZhO17_game)C++14
100 / 100
99 ms30344 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<ll, pll> #define fi first #define se second using namespace std; const int N = 1e6+5; const int M = 350; const ll mod = 1e9+9; const ll inf = 2e9; int m, k, t, n; int ans, a[N], b[N], c[N], h[N], d[N]; string s; vector<int> adj[N], kq; vector<int> val; mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); ll pw(ll k, ll n) { ll total =1 ; for(; n; n >>= 1) { if(n&1)total = total * k % mod; k = k * k % mod; } return total; } struct node { int l, r, val, lazy; node(){} node(int _l, int _r, int _val, int _lazy) { l = _l; r = _r; val = _val; lazy = _lazy; } }; vector<node> st; int build(int l, int r) { if(l == r) { st.pb(node(0, 0, b[l], 0)); return st.size()-1; } int mid = (l+r)>>1; node cur; cur.l = build(l, mid); cur.r = build(mid+1, r); cur.lazy = 0; cur.val = min(st[cur.l].val, st[cur.r].val); st.pb(cur); return st.size()-1; } struct BIT { int n; vector<int> fe; BIT(int _n) { n = _n; fe.resize(n+1, 0); } void add(int id, int x) { for(; id <= n; id += id & -id)fe[id] += x; } void add(int l, int r, int x) { if(l > r)swap(l, r); add(l, x); add(r, -x); } int get(int id) { int total = 0; for(; id; id -= id & -id)total += fe[id]; return total; } }; void sol(int icase) { cin >> n >> m; k = 1e6; BIT bit(k); for(int i = 1; i <= n; i ++)cin >> a[i]; for(int i = 2; i <= n; i ++) { bit.add(a[i-1], a[i], 1); if(i < n)bit.add(a[i], a[i], -1); } while(m -- > 0) { cin >> t; int x, y; if(t == 2) { cin >> x; cout << bit.get(x) << '\n'; } else { cin >> x >> y; if(x > 1)bit.add(a[x-1], a[x], -1); if(x < n)bit.add(a[x+1], a[x], -1); if(x > 1 && x < n)bit.add(a[x], a[x], 1); a[x] = y; if(x > 1)bit.add(a[x-1], a[x], 1); if(x < n)bit.add(a[x+1], a[x], 1); if(x > 1 && x < n)bit.add(a[x], a[x], -1); } } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; for(int i = 1; i <= test; i ++)sol(i); return 0; }

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:127:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:128:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...