제출 #577625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577625		Ronin13	Poklon (COCI17_poklon)	C++14	140 / 140	870 ms	72444 KiB

poklon

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 1e6 + 1;

vector <vector <int> > vec(NMAX);
vector <int> t(4  * NMAX);
int curind[NMAX];
void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] += val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin) return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l, m, st, fin) + get(2 * v + 1, m + 1, r, st, fin);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int q; cin >> q;
    int a[n + 1];
    map <int,int>mp;
    int b[n + 1];
    for(int i= 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort( b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        mp[b[i]] = i;
    }
    for(int i = 1; i <= n; i++) a[i] = mp[a[i]];
    for(int i = 1; i <= n; i++){
        vec[a[i]].pb(i);
        curind[a[i]] = 2;
    }
    vector <vector <pii> > qv(n  + 1);
    vector <int> res(q + 1);
    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        qv[l].pb({r, i});
    }
    for(int i = 1; i <= n; i++){
        curind[i] = 2;
        if(vec[i].size() < 2) {
            continue;
        }
        else{
            update(1, 1, n, vec[i][1], 1);
        }
        if(vec[i].size() >= 3) update(1, 1, n, vec[i][2], -1);
    }
    for(int l = 1; l <= n; l++){
        for(auto to : qv[l]){
            int r = to.f;
            int ans = get(1, 1, n, l, r);
            res[to.s] = ans;
        }
        if(curind[a[l]] > vec[a[l]].size()) continue;
        int ind = vec[a[l]][curind[a[l]] - 1];
        update(1, 1, n, ind, -1);
        if(curind[a[l]] == vec[a[l]].size()) continue;
        ind = vec[a[l]][curind[a[l]]];
        if(curind[a[l]] < vec[a[l]].size())update(1, 1, n, ind, 2);
        curind[a[l]]++;
        if(curind[a[l]] < vec[a[l]].size()) ind = vec[a[l]][curind[a[l]]], update(1, 1, n, ind, -1);
    }
    for(int i = 1; i <= q; i++) cout << res[i] << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

poklon.cpp: In function 'int main()':
poklon.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if(curind[a[l]] > vec[a[l]].size()) continue;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
poklon.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if(curind[a[l]] == vec[a[l]].size()) continue;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
poklon.cpp:83:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if(curind[a[l]] < vec[a[l]].size())update(1, 1, n, ind, 2);
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
poklon.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if(curind[a[l]] < vec[a[l]].size()) ind = vec[a[l]][curind[a[l]]], update(1, 1, n, ind, -1);
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140