oj.uz

Submission #541043

# Submission time Handle Problem Language Result Execution time Memory
541043 2022-03-22T07:06:17 Z LittleCube Fire (JOI20_ho_t5) C++14
6 / 100
 271 ms 15156 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct query
{
    int i, T, L, R;
};

ll N, Q, arr[200005], ans[200005], bit[200005];
query q[200005];

void bitmodify(int pos, ll val)
{
    for (int i = pos; i <= N; i += (i & -i))
        bit[i] += val;
}

ll bitquery(int pos)
{
    ll ans = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        ans += bit[i];
    return ans;
}

signed main()
{
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    for (int i = 1; i <= Q; i++)
    {
        cin >> q[i].T >> q[i].L >> q[i].R;
        q[i].i = i;
    }
    sort(q + 1, q + 1 + Q, [](query q1, query q2)
         { return q1.T < q2.T; });
    int qdx = 1;
    vector<pll> plus;
    int last = -1e9;
    for (int i = 1; i <= N; i++)
    {
        if (arr[i] == 1)
            plus.emplace_back(pll{i - last, i});
        else
            last = i;
    }
    sort(plus.begin(), plus.end());
    int pdx = 0;
    for (int i = 1; i <= N; i++)
        bitmodify(i, arr[i]);
    for (int i = 1; i <= N; i++)
    {
        while (pdx < plus.size() && plus[pdx].F == i)
        {
            bitmodify(plus[pdx].S, 1);
            pdx++;
        }
        while (qdx <= Q && q[qdx].T == i)
        {
            ans[q[qdx].i] = bitquery(q[qdx].R) - bitquery(q[qdx].L - 1);
            qdx++;
        }
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (pdx < plus.size() && plus[pdx].F == i)
      |                ~~~~^~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 271 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 270 ms 10344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 11076 KB Output is correct
2 Correct 258 ms 14648 KB Output is correct
3 Correct 236 ms 15032 KB Output is correct
4 Correct 243 ms 15012 KB Output is correct
5 Correct 231 ms 14956 KB Output is correct
6 Correct 230 ms 14708 KB Output is correct
7 Correct 230 ms 14936 KB Output is correct
8 Correct 237 ms 15156 KB Output is correct
9 Correct 231 ms 14960 KB Output is correct
10 Correct 230 ms 14804 KB Output is correct
11 Correct 243 ms 15104 KB Output is correct
12 Correct 234 ms 15004 KB Output is correct
13 Correct 236 ms 14912 KB Output is correct
14 Correct 265 ms 15028 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -