| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 340018 |
2020-12-26T15:19:58 Z |
Sprdalo |
Money (IZhO17_money) |
C++17 |
|
2 ms |
2412 KB |
#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
template<int MAXN>
struct segtr{
//To change the purpose of the segtree just redefine the operators
struct node{
int x;
node(int x = 0) : x(x) {}
node& operator+= (const node& other){
x += other.x;
return *this;
}
node operator+ (const node& other){
node tmp = *this;
return tmp += other;
}
};
node a[2*MAXN];
//Initialize the array
void init(){
for(int i = 1; i <= MAXN; ++i){
a[i+MAXN-1] = node{};
}
for(int i = MAXN-1; i > 0; --i){
a[i] = a[2*i] + a[2*i+1];
}
}
//Sets the node and updates the tree
void set(int pos, node val){
pos += MAXN-1;
a[pos] = val;
while(pos > 1){
pos /= 2;
a[pos] = a[2*pos] + a[2*pos+1];
}
}
inline void add(int pos, node val){ //Just forwards to set
set(pos, node{a[pos+MAXN-1]+val});
}
//Gets the range query
node get(int l, int r, int pos = 1, int rl = 1, int rr = MAXN){
if(r < rl || rr < l){ return node{}; }
if(l <= rl && rr <= r){ return a[pos]; }
int rm = (rl+rr)/2;
return get(l, r, 2*pos, rl, rm) + get(l, r, 2*pos+1, rm+1, rr);
}
};
segtr<131072> drvo;
map<int, int> m;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
int n;
cin >> n;
vi a(n);
set<int> s;
for (auto& i : a){
cin >> i;
s.insert(i);
}
int cur = 1;
for (auto& i : s){
m[i] = cur++;
}
for (auto& i : a)
i = m[i];
drvo.init();
int l = a[0], sol = 1;
drvo.set(a[0], 1);
for (int i = 1; i < n; ++i){
l = a[i-1];
drvo.set(a[i], 1);
if (a[i] < l){
++sol;
continue;
}
if (l+1>a[i]-1){
continue;
}
if (drvo.get(l+1,a[i]-1).x == 0){
continue;
} else {
++sol;
}
}
cout<< sol << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2412 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2412 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
