Submission #375132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375132	2021-03-09T03:31:32 Z	Nordway	Po (COCI21_po)	C++17	70 / 70	25 ms	1516 KB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=1e5+11;
const int M=1e6+1;
const ll inf=1e9+11;
const ld EPS=1e-6;
const ll INF=1e18;
const ll mod=/*999999001*/1e9+7;
const int dx[4]={1,2,2,-1};
const int dy[4]={2,1,-1,2};

pair<int,int>a[N];

int t[N];

void upd(int x){
  for(int i=x;i<N;i=(i|(i+1))){
    t[i]++;
  }
}

int get(int x){
  int res=0;
  for(int i=x;i>=0;i=(i&(i+1))-1){
    res+=t[i];
  }
  return res;
}

void solve(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].x;
    a[i].y=i;
  }
  sort(a+1,a+n+1);
  int pre=0;
  int ans=0;
  for(int i=1;i<=n;i++){
    if(a[i].x!=a[i-1].x){
      pre=0;
      ans++;
    }
    else if(get(a[i].y)-get(pre))ans++;
    upd(a[i].y);
    pre=a[i].y;
  }
  cout<<ans;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int T=1;
  //cin>>T;
  for(int i=1;i<=T;i++){
    solve();
    cout<<nl;
  }
  return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	13 ms	1004 KB	Output is correct
5	Correct	17 ms	1260 KB	Output is correct
6	Correct	25 ms	1516 KB	Output is correct
7	Correct	15 ms	1516 KB	Output is correct