Submission #473395

#	Time	Username	Problem	Language	Result	Execution time	Memory
473395		hjc4vr	Baloni (COCI15_baloni)	C++14	100 / 100	118 ms	13168 KiB

baloni

#include <bits/stdc++.h>
#define int long long
#define pp pair <bool,int>
#define ppi pair <int,int>
#define tp tuple <int,int,int,bool>
#define c1(x) cin >> x
#define c2(x,y) cin >> x >> y
#define c3(x,y,z) cin >> x >> y >> z
#define c4(x,y,z,f) cin>> x >> y >> z >> f
#define mp(a,b) make_pair(a,b)
//typedef long long ll;
//
//int power(int a,int b){
//    int result=1;
//    while (b>0){
//        if (b%2==1) result *= a;
//        a = a*a;
//        b /= 2;
//    }
//    return result;
//} // power(2,3) = 8;
using namespace std;
//int dp[200000];
//struct func{
//    int m,c;
//    int operator () (int x) const{
//        return m*x + c;
//    }
//    func (int mm,int cc){
//        m=mm,c=cc;
//    }
//};
//
//struct node{ // how to delay
//    int s,e;
//    func f={0,1000000009};
//    node *l,*r;
//    node(int ss,int ee){
//        s = ss, e =ee;
//        int m = (s+e)/2;
//        if (s==e){
//            l=r=NULL;
//        }else{
//            l = new node(s,m);
//            r = new node(m+1,e);
//        }
//    }
//    int query(int x){
//        if (s==e) return f(x);
//        int m=(s+e)/2;
//        int ans = f(x);
//        if (x>m) ans = min(ans,r->query(x));
//        else if (x<=m)  ans = min(ans,l->query(x));
//        return ans;
//    }
//    void update(func n){
//        int m = (s+e)/2;
//        bool mid = n(m) < f(m);
//        bool start = n(s) < f(s);
//        if (mid){
//            swap(n,f);
//        }
//        if (s==e) return;
//        if (!mid==start){
//            l->update(n);
//        }else{
//            r->update(n);
//        }
//    }
//} *root;
//
//bool yea[100005];
//
//string ans="";
//int n,k;
//int LOG=19;
//int spt[500005][20];
//int ps[500005],ps1[500005];
//
//
//int query(int l,int r){
//    int length = r-l+1;
//    int le = log2(length);  //2
//    return max(spt[l][le],spt[r-(1<<(le))+1][le]);
//}
//
//struct fraction{
//    int a,b,car1,car2; // a = (x2-x1), b = (v2-v1)
//    bool operator > (const fraction &f) const {
//        return (a)*(f.b) > (f.a)*(b);
//    }
//};
//int cnt=0;
//int pre[100005],post[100005],parent[100005][17],depth[100005],in[100005],out[100005],distanc[100005],T[100005];
//void update(int x,int val,int vec[]){
//    for (;x<=100005;x+=x&(-x)) vec[x] += val;
//}
//int query(int x,int vec[]){
//    int result=0;
//    for (;x!=0;x-=x&(-x)) result += vec[x];
//    return result;
//}
//vector<tuple<int,int,int>> arr[100005];
//void dfs(int x,int par,int dep,int dis,int t){
//    parent[x][0] = par;
//    depth[x] = dep;
//    pre[x] = cnt;
//    distanc[x] = dis;
//    T[x] = t;
//    for (int i=1;i<17;++i){
//        parent[x][i] = parent[parent[x][i-1]][i-1];
//    }
//    for (tuple<int,int,int> tup: arr[x]){
//        if (get<0>(tup)!=par){
//            dfs(get<0>(tup),x,dep+1,dis+get<2>(tup),t+get<3>(tup));
//        }
//    }
//    post[x] = cnt;
//}
//
//int lca(int a,int b){
//    if (depth[a]<depth[b]) swap(a,b);
//    int dif = depth[a] - depth[b];
//    for (int i=0;i<17;++i){
//        if ((1<<i)&dif){
//            a = parent[a][i];
//        }
//    }
//    if (a==b) return a;
//    for (int i=16;i>=0;--i){
//        if (parent[a][i]!=parent[b][i]){
//            a = parent[a][i];
//            b = parent[b][i];
//        }
//    }
//    return a;
//}
//
//void init(int x,int val,int par){
//    update(pre[par],distanc[x]*val,out);
//    update(post[par],-distanc[x]*val,out);
//    update(pre[x],distanc[par]*val,in);
//    update(post[x],-distanc[par]*val,in);
//    for (tuple<int,int,int> tup:arr[x]){
//        if (get<0>(tup)!=par){
//            init(get<0>(tup),get<3>(tup),x);
//        }
//    }
//}
//void solve(){
//    int n,G,start=-1;cin>>n>>G;
//    for (int i=0;i<n-1;++i){
//        int a,b,c,d;cin>>a>>b>>c>>d;
//        if (start==-1) start = a;
//        arr[a].push_back({b,c,d});
//        arr[b].push_back({a,c,d});
//    }
//    dfs(start,start,0,0,0);
//    init(start,0,start);
//    int q;cin>>q;
//    for (int qer=0;qer<n;++qer){
//        int a;cin>>a;
//        if (a==1){
//            int x,y;cin>>x>>y;
//            int sum = (G)*(distanc[x]+distanc[y]-distanc[lca(x,y)]);
//            //sum from  to lca
//            sum+=distanc[x]*(T[x]+T[y]-T[lca(x,y)]); //d[c]
//            sum-= query(pre[lca(x,y)],in) - query(post[x],in);
//            sum+= query(pre[lca(x,y)],out) - query(post[y],out);
//            cout << sum;
//        }
//    }
//}

struct node{
    int s,e,v=0;
    node *l,*r;
    node (int ss,int ee){
        s=ss,e=ee;
        if (s!=e){
            l=new node(s,(s+e)/2);
            r=new node((s+e)/2+1,e);
        }else{
            l=r=NULL;
        }
    }
    int query(int a,int b){
        if (a>=s and b<=e) return v;
        int result=0;
        if (a<s) result += l->query(a,b);
        if (b>e) result += r->query(a,b);
        return result;
    }
    void update(int x,int val){
        if (s==e) v+= val;
        else{
            if (x>(s+e)/2){
                r->update(x,val);
            }
            if (x<=(s+e)/2){
                l->update(x,val);
            }
        }
        v = r->v + l->v;
    }
} *root;
int color[100005],pos1[100005],pre1[100005],ft2[100005];
bool visited[100005];
vector<int> ar[100005];
int cnt1=1;
void update(int x,int val){
    for (;x<=100005;x+=x&(-x)) ft2[x] += val;
}
int query(int x){
    int result=0;
    for (;x!=0;x-=x&(-x)) result += ft2[x];
    return result;
}
void dfss(int x,int par){
    pre1[x] = cnt1;
    cnt1++;
    for (int y:ar[x]){
        if (y!=par and !visited[y]) dfss(y,x);
    }
    pos1[x] = cnt1;
}
void solve1(){
    int n;cin>>n;
    vector<int> arr(n);
    for (int i=0;i<n;++i){
        cin >> arr[i];
    }
    unordered_map<int,int> mp;
//    for (int i=0;i<n;++i){
//        cout << arr[i];
//    }
    int ans=0;
    for (int i=0;i<n;++i){
        if (mp.find(arr[i])==mp.end() or mp[arr[i]]==0){
//            cout << arr[i];
            ans++;
            mp[arr[i]-1] += 1;
        }else{
            mp[arr[i]] -= 1;
            mp[arr[i]-1] += 1;
        }
    }
    cout << ans;

}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    solve1();
//    string str="hello world hey";
//    cout << str.substr(0,3);

}

• Subtask 1: 100 / 100