| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 473395 |
2021-09-15T13:02:50 Z |
hjc4vr |
Baloni (COCI15_baloni) |
C++14 |
|
118 ms |
13168 KB |
#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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2732 KB |
Output is correct |
| 5 |
Correct |
110 ms |
12548 KB |
Output is correct |
| 6 |
Correct |
118 ms |
13168 KB |
Output is correct |
| 7 |
Correct |
96 ms |
11272 KB |
Output is correct |
| 8 |
Correct |
93 ms |
11128 KB |
Output is correct |
| 9 |
Correct |
117 ms |
11820 KB |
Output is correct |
| 10 |
Correct |
102 ms |
12068 KB |
Output is correct |
