oj.uz

Submission #1025405

# Submission time Handle Problem Language Result Execution time Memory
1025405 2024-07-17T01:55:02 Z Thanhs Index (COCI21_index) C++14
110 / 110
 534 ms 32884 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define pb push_back
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
 
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
 
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int p = 31;

struct Query
{
    int l, r, lx, rx, m, cur;
}Q[N];

int n, q, a[N], bit[N];
vector<pair<int, int>> ops[N];

void upd(int i)
{
    for (; i <= 2e5; i+= i & -i)
        bit[i]++;
}

int get(int i)
{
    int res = 0;
    for (; i; i -= i & -i)
        res += bit[i];
    return res;
}

signed main()
{
    if (fopen("in.txt", "r")) {
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    }
    fastIO
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= q; i++)
    {
        cin >> Q[i].l >> Q[i].r; 
        Q[i].lx = 1, Q[i].rx = Q[i].r - Q[i].l + 2;
    }
    while (1)
    {
        bool changed = 0;
        for (int i = 1; i <= q; i++)
            if (Q[i].lx < Q[i].rx - 1)
            {
                Q[i].m = Q[i].lx + Q[i].rx >> 1;
                Q[i].cur = 0;
                ops[Q[i].l - 1].push_back({i, -1});
                ops[Q[i].r].push_back({i, 1});
            }
        memset(bit, 0, sizeof bit);
        ops[0].clear();
        for (int i = 1; i <= n; i++)
        {
            upd(a[i]);
            for (auto p : ops[i])
                Q[p.fi].cur += p.se * (get(2e5) - get(Q[p.fi].m - 1));
            ops[i].clear();
        }
        for (int i = 1; i <= q; i++)
            if (Q[i].lx < Q[i].rx - 1)
            {
                if (Q[i].cur >= Q[i].m)
                    Q[i].lx = Q[i].m;
                else
                    Q[i].rx = Q[i].m;
                changed = true;

            }
        if (!changed) break;
    }
    for (int i = 1; i <= q; i++)
        cout << Q[i].lx << endl;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:67:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |                 Q[i].m = Q[i].lx + Q[i].rx >> 1;
      |                          ~~~~~~~~^~~~~~~~~
index.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("in.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
index.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("out.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8916 KB Output is correct
4 Correct 3 ms 8924 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8932 KB Output is correct
7 Correct 4 ms 8920 KB Output is correct
8 Correct 3 ms 8920 KB Output is correct
9 Correct 4 ms 8924 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8916 KB Output is correct
4 Correct 3 ms 8924 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8932 KB Output is correct
7 Correct 4 ms 8920 KB Output is correct
8 Correct 3 ms 8920 KB Output is correct
9 Correct 4 ms 8924 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 78 ms 14676 KB Output is correct
12 Correct 78 ms 14556 KB Output is correct
13 Correct 79 ms 14420 KB Output is correct
14 Correct 78 ms 14416 KB Output is correct
15 Correct 78 ms 14512 KB Output is correct
16 Correct 78 ms 14480 KB Output is correct
17 Correct 81 ms 14416 KB Output is correct
18 Correct 87 ms 14572 KB Output is correct
19 Correct 82 ms 14420 KB Output is correct
20 Correct 88 ms 14560 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8916 KB Output is correct
4 Correct 3 ms 8924 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8932 KB Output is correct
7 Correct 4 ms 8920 KB Output is correct
8 Correct 3 ms 8920 KB Output is correct
9 Correct 4 ms 8924 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 78 ms 14676 KB Output is correct
12 Correct 78 ms 14556 KB Output is correct
13 Correct 79 ms 14420 KB Output is correct
14 Correct 78 ms 14416 KB Output is correct
15 Correct 78 ms 14512 KB Output is correct
16 Correct 78 ms 14480 KB Output is correct
17 Correct 81 ms 14416 KB Output is correct
18 Correct 87 ms 14572 KB Output is correct
19 Correct 82 ms 14420 KB Output is correct
20 Correct 88 ms 14560 KB Output is correct
21 Correct 421 ms 32848 KB Output is correct
22 Correct 416 ms 32704 KB Output is correct
23 Correct 448 ms 32848 KB Output is correct
24 Correct 473 ms 32884 KB Output is correct
25 Correct 462 ms 32852 KB Output is correct
26 Correct 534 ms 32808 KB Output is correct
27 Correct 424 ms 32852 KB Output is correct
28 Correct 482 ms 32728 KB Output is correct
29 Correct 441 ms 32852 KB Output is correct
30 Correct 464 ms 32740 KB Output is correct