oj.uz

Submission #99237

# Submission time Handle Problem Language Result Execution time Memory
99237 2019-03-01T19:58:16 Z Milki Poklon (COCI17_poklon) C++14
0 / 140
 731 ms 40296 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;
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12160 KB Output isn't correct
2 Incorrect 13 ms 12160 KB Output isn't correct
3 Incorrect 31 ms 12228 KB Output isn't correct
4 Incorrect 21 ms 12416 KB Output isn't correct
5 Incorrect 116 ms 17456 KB Output isn't correct
6 Incorrect 123 ms 17676 KB Output isn't correct
7 Incorrect 278 ms 23156 KB Output isn't correct
8 Incorrect 420 ms 28892 KB Output isn't correct
9 Incorrect 544 ms 34456 KB Output isn't correct
10 Incorrect 731 ms 40296 KB Output isn't correct