oj.uz

Submission #254490

# Submission time Handle Problem Language Result Execution time Memory
254490 2020-07-30T06:24:54 Z IgorI Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

vi countScans(vi a, vi x, vi v)
{
    int n = a.size(), q = x.size();
    vi ans(q);
    for (int i = 0; i < q; i++)
    {
        a[x[i]] = v[i];
        int res = 0;
        for (int j = 0; j < n; j++)
        {
            int z = 0;
            for (int k = 0; k < j; k++)
            {
                if (a[k] > a[j])
                {
                    z++;
                }
            }
            res = max(res, z);
        }
        ans[i] = res;
    }
    return ans;
}

#ifdef LOCAL
signed main()
{
    int n, q;
    cin >> n >> q;
    vi a(n), x(q), v(q);
    forn(i, n) cin >> a[i];
    forn(i, q) cin >> x[i] >> v[i];
    vi ans = countScans(a, x, v);
    forn(i, q) cout << ans[i] << "\n";
}
#endif // LOCAL

/*
4 2
1 2 3 4
0 3
2 1
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 384 KB Output is correct
2 Correct 220 ms 412 KB Output is correct
3 Correct 3075 ms 460 KB Output is correct
4 Correct 3075 ms 460 KB Output is correct
5 Correct 3103 ms 460 KB Output is correct
6 Correct 3185 ms 472 KB Output is correct
7 Correct 3093 ms 464 KB Output is correct
8 Correct 3103 ms 504 KB Output is correct
9 Correct 3116 ms 504 KB Output is correct
10 Correct 3080 ms 504 KB Output is correct
11 Correct 3112 ms 452 KB Output is correct
12 Correct 3116 ms 456 KB Output is correct
13 Correct 3062 ms 452 KB Output is correct
14 Correct 3088 ms 452 KB Output is correct
15 Correct 3072 ms 504 KB Output is correct
16 Correct 3076 ms 448 KB Output is correct
17 Correct 3129 ms 456 KB Output is correct
18 Correct 3110 ms 384 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 384 KB Output is correct
2 Correct 220 ms 412 KB Output is correct
3 Correct 3075 ms 460 KB Output is correct
4 Correct 3075 ms 460 KB Output is correct
5 Correct 3103 ms 460 KB Output is correct
6 Correct 3185 ms 472 KB Output is correct
7 Correct 3093 ms 464 KB Output is correct
8 Correct 3103 ms 504 KB Output is correct
9 Correct 3116 ms 504 KB Output is correct
10 Correct 3080 ms 504 KB Output is correct
11 Correct 3112 ms 452 KB Output is correct
12 Correct 3116 ms 456 KB Output is correct
13 Correct 3062 ms 452 KB Output is correct
14 Correct 3088 ms 452 KB Output is correct
15 Correct 3072 ms 504 KB Output is correct
16 Correct 3076 ms 448 KB Output is correct
17 Correct 3129 ms 456 KB Output is correct
18 Correct 3110 ms 384 KB Output is correct
19 Execution timed out 9076 ms 640 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9054 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 384 KB Output is correct
2 Correct 220 ms 412 KB Output is correct
3 Correct 3075 ms 460 KB Output is correct
4 Correct 3075 ms 460 KB Output is correct
5 Correct 3103 ms 460 KB Output is correct
6 Correct 3185 ms 472 KB Output is correct
7 Correct 3093 ms 464 KB Output is correct
8 Correct 3103 ms 504 KB Output is correct
9 Correct 3116 ms 504 KB Output is correct
10 Correct 3080 ms 504 KB Output is correct
11 Correct 3112 ms 452 KB Output is correct
12 Correct 3116 ms 456 KB Output is correct
13 Correct 3062 ms 452 KB Output is correct
14 Correct 3088 ms 452 KB Output is correct
15 Correct 3072 ms 504 KB Output is correct
16 Correct 3076 ms 448 KB Output is correct
17 Correct 3129 ms 456 KB Output is correct
18 Correct 3110 ms 384 KB Output is correct
19 Execution timed out 9076 ms 640 KB Time limit exceeded
20 Halted 0 ms 0 KB -