oj.uz

Submission #402506

# Submission time Handle Problem Language Result Execution time Memory
402506 2021-05-11T19:59:03 Z NintsiChkhaidze Poklon (COCI17_poklon) C++14
140 / 140
 926 ms 43424 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (node<<1),l,(l+r)>>1
#define right ((node<<1)|1),((l+r)>>1)+1,r
using namespace std;
const int N = 500005;
pair<int,int> b[N];
vector <pair<int,int>> v[N];
int a[N],ind[4][N],sgt[4*N],ans[N];
void upd(int node,int l,int r,int ind,int val){
    if (l == r){
        sgt[node] = val;
        return;
    }
    if (ind > ((l+r)>>1)) upd(right,ind,val);
    else upd(left,ind,val);
    sgt[node] = sgt[(node<<1)] + sgt[((node<<1)|1)];
}
ll get(int node,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return sgt[node];
    ll x = get(left,L,R),y = get(right,L,R);
    return x+y;
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,m;
    cin>>n>>m;
    
    for (int i=1;i<=n;i++)
        cin>>b[i].f,b[i].s=i;

    sort(b+1,b+n+1);
    a[b[1].s] = 1;
    for (int i=2;i<=n;i++){
        a[b[i].s] = a[b[i - 1].s];
        if (b[i].f > b[i-1].f) a[b[i].s]++;
    }
    
    for (int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        v[l].pb({r,i});
    }
    
    for (int i=n;i>=1;i--){
        if (ind[3][a[i]]) upd(1,1,n,ind[3][a[i]],0);
        if (ind[2][a[i]]) upd(1,1,n,ind[2][a[i]],-1);
        if (ind[1][a[i]]) upd(1,1,n,ind[1][a[i]],1);
        
        for (int j=0;j<v[i].size();j++){
            int r = v[i][j].f,ind = v[i][j].s;
            ans[ind] = get(1,1,n,i,r);
        }
        
        ind[3][a[i]] = ind[2][a[i]];
        ind[2][a[i]] = ind[1][a[i]];
        ind[1][a[i]] = i;
    }
    
    for (int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j=0;j<v[i].size();j++){
      |                      ~^~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12108 KB Output is correct
2 Correct 9 ms 12028 KB Output is correct
3 Correct 9 ms 12080 KB Output is correct
4 Correct 14 ms 12364 KB Output is correct
5 Correct 153 ms 18224 KB Output is correct
6 Correct 154 ms 18200 KB Output is correct
7 Correct 351 ms 24892 KB Output is correct
8 Correct 544 ms 32484 KB Output is correct
9 Correct 704 ms 37948 KB Output is correct
10 Correct 926 ms 43424 KB Output is correct