제출 #99237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99237		Milki	Poklon (COCI17_poklon)	C++14	0 / 140	731 ms	40296 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;
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);
      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: 0 / 140