Submission #380629

#TimeUsernameProblemLanguageResultExecution timeMemory
380629BeanZPoklon (COCI17_poklon)C++14
140 / 140
1800 ms33628 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 5e5 + 5; long long mod = 1e9 + 7; const int lim = 2e5; const int lg = 19; const int base = 700; const long double eps = 1e-6; struct viet{ ll l, r, id; bool operator <(const viet &o){ if ((l / base) == (o.l / base)) return r < o.r; return (l / base) < (o.l / base); } }; ll cnt[N], a[N], ans[N]; ll now = 0; void add(ll u){ if (cnt[a[u]] == 1) now++; if (cnt[a[u]] == 2) now--; cnt[a[u]]++; } void del(ll u){ if (cnt[a[u]] == 3) now++; if (cnt[a[u]] == 2) now--; cnt[a[u]]--; } viet Q[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("tests.inp", "r", stdin); freopen("tests.out", "w", stdout); } ll n, q; cin >> n >> q; vector<ll> val; for (int i = 1; i <= n; i++) cin >> a[i], val.push_back(a[i]); sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); for (int i = 1; i <= n; i++){ a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1; } for (int i = 1; i <= q; i++){ cin >> Q[i].l >> Q[i].r; Q[i].id = i; } sort(Q + 1, Q + q + 1); ll l = 1, r = 0; for (int i = 1; i <= q; i++){ while (r > Q[i].r){ del(r); r--; } while (l < Q[i].l){ del(l); l++; } while (r < Q[i].r){ r++; add(r); } while (l > Q[i].l){ l--; add(l); } ans[Q[i].id] = now; } for (int i = 1; i <= q; i++){ cout << ans[i] << endl; } } /* Ans: Out: */

Compilation message (stderr)

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