oj.uz

Submission #81469

# Submission time Handle Problem Language Result Execution time Memory
81469 2018-10-24T19:15:22 Z inom Simple game (IZhO17_game) C++14
49 / 100
 428 ms 24120 KB 
#include <bits/stdc++.h>
 
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );
 
using namespace std;
 
const int N = 100100;
 
int TN = 1;
 
multiset<pair<int, int> > st;
 
int a[N];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    /// -------------------------------------
    // fin("game.in"); fout("game.out");
    /// cin >> TN;
    /// -------------------------------------
    int n, m;
    cin >> n >> m;
    if (n <= 1000 && m <= 1000) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int t, pos, new_val, x;
        for (int i = 1; i <= m; i++) {
            cin >> t;
            if (t == 1) {
                cin >> pos >> new_val;
                a[pos] = new_val;
            }
            else {
                int cnt = 0;
                cin >> x;
                for (int j = 1; j < n; j++) {
                    if ((a[j] <= x && x <= a[j + 1]) || (a[j + 1] <= x && x <= a[j])) {
                        cnt++;
                    }
                }
                cout << cnt << endl;
            }
        }
        return 0;
    }
    else {
    multiset<pair<int, int> > st;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1) {
            st.insert(make_pair(min(a[i], a[i - 1]), 0));
            st.insert(make_pair(max(a[i], a[i - 1]), INT_MAX));
        }
    }
    int t, h;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        if (t == 2) {
            cin >> h;
            st.insert(make_pair(h, i));
        }
    }
    multiset<pair<int, int> > :: iterator it;
    vector<int> ans(N);
    int cnt = 0;
    for (it = st.begin(); it != st.end(); it++) {
        pair<int, int> p = *it;
        if (p.second == 0) cnt++;
        if (p.second > 0 && p.second < INT_MAX) ans[p.second] = cnt;
        if (p.second == INT_MAX) cnt--;
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << endl;
    }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 7 ms 908 KB Output is correct
6 Correct 5 ms 908 KB Output is correct
7 Correct 5 ms 908 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 7 ms 908 KB Output is correct
6 Correct 5 ms 908 KB Output is correct
7 Correct 5 ms 908 KB Output is correct
8 Correct 290 ms 16860 KB Output is correct
9 Correct 397 ms 18936 KB Output is correct
10 Correct 428 ms 20636 KB Output is correct
11 Correct 266 ms 20852 KB Output is correct
12 Correct 377 ms 22648 KB Output is correct
13 Correct 327 ms 24120 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 7 ms 908 KB Output is correct
6 Correct 5 ms 908 KB Output is correct
7 Correct 5 ms 908 KB Output is correct
8 Correct 290 ms 16860 KB Output is correct
9 Correct 397 ms 18936 KB Output is correct
10 Correct 428 ms 20636 KB Output is correct
11 Correct 266 ms 20852 KB Output is correct
12 Correct 377 ms 22648 KB Output is correct
13 Correct 327 ms 24120 KB Output is correct
14 Incorrect 350 ms 24120 KB Output isn't correct
15 Halted 0 ms 0 KB -