oj.uz

Submission #51326

# Submission time Handle Problem Language Result Execution time Memory
51326 2018-06-17T13:32:53 Z Nicksechko Money (IZhO17_money) C++14
0 / 100
 1500 ms 700 KB 
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <queue>
#include <unordered_map>
//#include <unordered_set>
#include <iomanip>
#include <stack>
#include <ctime>
#include <cassert>
#include <cmath>

#define y1 ups
#define left lll
#define right rrr
#define next nnn
//#define find fff

typedef unsigned long long ull;

using namespace std;

//mt19937_64 twister(chrono::steady_clock().now().time_since_epoch().count());
//mt19937_64 twister(8888);
//
//long long rnd(long long l, long long r)
//{
//    uniform_int_distribution<long long> dis(l, r);
//    return dis(twister);
//}

const int mod = (int)1e9 + 9;
//const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
//const int st[2] = {887, 8887};'
const int maxn = 588;
const int inf = 1e4 + 88;
const int logn = 22;
const int maxa = 500*500 + 88;
const int block = 775;
const long long infll = 1e18 + 88;
const char sgl[5] = {'a', 'e', 'i', 'o', 'u'};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int knightx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int knighty[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int kingx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int kingy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const char sep = 'a' - 1;
const double eps = 1e-9;
const int maxn1 = 1e3 + 88;

//#define int long long

set<int> s;
int a[maxn];

void solve()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ifstream cin("bootfall.in");
//    ofstream cout("bootfall.out");
    int n, ans = 0, i = 0;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];
    i = 0;
    while (i < n)
    {
        int rg = inf, lg = 0;
        auto it = s.upper_bound(a[i]);
        if (it != s.end())
            rg = *it;
        if (it != s.begin())
            lg = *(--it);
        ans++;
        while (i < n && lg <= a[i] && a[i] <= rg)
        {
            lg = max(lg, a[i]);
            s.insert(a[i]);
            i++;
        }
    }
    cout << ans;
}

//#undef int

int main()
{
//    srand(time(0));
//    srand(8);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
//    ifstream cin("output.txt");
//    ifstream fin("12.out");
//    int a, b, i = 0;
//    while (cin >> a)
//    {
//        fin >> b;
//        if (a != b)
//        {
//            cout << i << " " << a << " " << b;
//            return 0;
//        }
//        i++;
//    }
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    freopen("f.in", "r", stdin);
//    freopen("f.out", "w", stdout);
//    int t = 10000;
//    while (t--)
//    {
//        if (t == 9947)
//            t = 9947;
//        gen();
//        cout << t << endl;
//        brut();
//        if (!solve())
//        {
//            cout << "kek";
//            return 0;
//        }
//    }
    solve();
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Execution timed out 1570 ms 700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Execution timed out 1570 ms 700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Execution timed out 1570 ms 700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Execution timed out 1570 ms 700 KB Time limit exceeded
8 Halted 0 ms 0 KB -