Submission #99238

#	Time	Username	Problem	Language	Result	Execution time	Memory
99238		Milki	Poklon (COCI17_poklon)	C++14	140 / 140	882 ms	29176 KiB

poklon

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 5e5 + 5;

int n, q;
int a[MAXN];
vector <point> query[MAXN];

struct Logaritamska{
  int loga[MAXN];
  void add(int x, int val){
    for(; x < MAXN; x += (x & (-x)))
      loga[x] += val;
  }
  int get(int x){
    int ret = 0;
    for(; x > 0; x -= (x & (-x)))
      ret += loga[x];
    return ret;
  }
  int sum(int l, int r){
    if(l) return get(r) - get(l - 1);
    else return get(r);
  }
} L;

map <int, int> last1, last2, last3;
int sol[MAXN];

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> q;
  REP(i, n) cin >> a[i + 1];
  REP(i, q) { int l, r; cin >> l >> r; query[r].pb( point(l, i) ); }

  FOR(i, 1, n + 1){
    if(last1.find(a[i]) != last1.end()){
      if(last2.find(a[i]) != last2.end()){
          L.add(last2[a[i]], -2);
          if(last3.find(a[i]) != last3.end())
            L.add(last3[a[i]], 1);
          last3[a[i]] = last2[a[i]];
      }
      last2[a[i]] = last1[a[i]];
      last1[a[i]] = i;
      L.add(last2[a[i]], 1);
    }
    else{
      last1[a[i]] = i;
    }

    for(auto it : query[i]){
      sol[it.second] = L.sum(it.first, i);
    }
  }
  REP(i, q)
    cout << sol[i] << "\n";
}

• Subtask 1: 140 / 140