oj.uz

Submission #99238

# Submission time Handle Problem Language Result Execution time Memory
99238 2019-03-01T20:03:02 Z Milki Poklon (COCI17_poklon) C++14
140 / 140
 882 ms 29176 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12160 KB Output is correct
2 Correct 13 ms 12160 KB Output is correct
3 Correct 14 ms 12132 KB Output is correct
4 Correct 18 ms 12288 KB Output is correct
5 Correct 99 ms 15480 KB Output is correct
6 Correct 135 ms 15624 KB Output is correct
7 Correct 316 ms 19168 KB Output is correct
8 Correct 536 ms 22392 KB Output is correct
9 Correct 675 ms 25768 KB Output is correct
10 Correct 882 ms 29176 KB Output is correct