Submission #523642

#TimeUsernameProblemLanguageResultExecution timeMemory
523642tube5429Poklon (COCI17_poklon)C++14
140 / 140
2199 ms270388 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--) #define R0F(i,a) ROF(i,0,a) #define REP(a) F0R(_,a) #define each(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define rsz resize #define pb push_back #define f first #define s second #define pf push_front #define ft front() #define bk back() #define eb emplace_back #define lb lower_bound #define ub upper_bound #define tcT template<class T #define tcTU tcT, class U #define nl "\n" using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vb = vector<bool>; using pi = pair<int,int>; using vpi = vector<pi>; using str = string; using vs = vector<str>; using db = double; using pl = pair<ll,ll>; using pd = pair<db,db>; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; tcTU> using PR = pair<T,U>; const int MOD = 1e9+7; const ll INF = 1e18; const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } constexpr bool onbit(int msk, int i) { return msk>>i&1; } constexpr ll p2(int x) { return 1LL<<x; } constexpr int pct(int x) { return __builtin_popcount(x); } constexpr int lg2(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }; //int only tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b,1 : 0; } ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } tcTU> T fstTrue(T lo, T hi, U f) { hi++; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; } tcTU> T lstTrue(T lo, T hi, U f) { lo--; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; } tcT> void remDup(V<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); } void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL void setPrec() { cout << fixed << setprecision(16); } void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); setPrec(); if(sz(NAME)) { freopen((NAME + ".in").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } const int MX = 5e5+5; int N,Q, A[MX], ls[MX], rs[MX], lef[MX], rig[MX], ans[MX]; vpi T[MX*4 + 15]; void upd(int x, int l, int r, int L, int v) { if(L > r || L < l) return; T[x].pb({rs[v], v}); int mid = (l+r)>>1; if(l == r) return; upd(x<<1, l, mid , L, v); upd(x<<1|1, mid+1, r, L, v); } void qryupd(int x, int l, int r, int L, int R, int p1, int p2) { if(L > r || R < l) return; if(l >= L && r <= R) { T[x].pb({p1, -1}); T[x].pb({p2, -2}); return; } int mid = (l + r)>>1; qryupd(x<<1, l, mid, L, R, p1, p2); qryupd(x<<1|1, mid+1, r, L, R, p1, p2); } void calc(int x, int l, int r) { sort(all(T[x])); int cnt = 0; each(v, T[x]) { if(v.s == -1) ++cnt; else if(v.s == -2) --cnt; else ans[v.s] += cnt; } if(l == r) return; int mid = (l + r) >> 1; calc(x<<1, l, mid); calc(x<<1|1, mid+1, r); } void solve() { cin>>N>>Q; F0R(i,N) cin>>A[i]; F0R(i,Q) { cin>>ls[i]>>rs[i]; ls[i]--; rs[i]--; upd(1, 0, N-1, ls[i], i); } map<int,int> M; F0R(i,N) { int pos = -1; if(M.count(A[i])) pos = M[A[i]]; lef[i] = pos; M[A[i]] = i; } M.clear(); R0F(i,N) { int pos = N; if(M.count(A[i])) pos = M[A[i]]; rig[i] = pos; M[A[i]] = i; } rig[N] = N; F0R(i,N) { int rpos = rig[i]; if(rpos == N) continue; qryupd(1,0,N-1, lef[i]+1, i, rpos, rig[rpos]); } calc(1, 0, N-1); F0R(i,Q) cout << ans[i] << nl; } int main() { setIO(); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

Compilation message (stderr)

poklon.cpp: In function 'void setIO(std::string)':
poklon.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen((NAME + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   freopen((NAME + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...