oj.uz

답안 #202631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202631 2020-02-17T11:29:57 Z SamAnd Fire (JOI20_ho_t5) C++17
6 / 100
 329 ms 22512 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
struct ban
{
    int t, l, r;
};

int n, m;
int s[N];
ban b[N];

int ss[N];
void solv1()
{
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
            ss[j] = s[j];
        for (int ii = 0; ii < b[i].t; ++ii)
        {
            for (int j = n; j >= 1; --j)
                ss[j] = max(ss[j], ss[j - 1]);
        }
        long long ans = 0;
        for (int j = b[i].l; j <= b[i].r; ++j)
            ans += ss[j];
        printf("%lld\n", ans);
    }
}

int t[N * 4];
void bil(int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = s[tl];
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qry(tl, m, l, r, pos * 2);
    if (l > m)
        return qry(m + 1, tr, l, r, pos * 2 + 1);
    return max(qry(tl, m, l, m, pos * 2),
               qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}

long long p[N];
void solv2()
{
    bil(1, n, 1);
    for (int i = 1; i <= n; ++i)
        s[i] = qry(1, n, max(1, i - b[1].t), i, 1);
    for (int i = 1; i <= n; ++i)
        p[i] = p[i - 1] + s[i];
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", p[b[i].r] - p[b[i].l - 1]);
}

void solv3()
{
    bil(1, n, 1);
    for (int i = 1; i <= m; ++i)
    {
        printf("%d\n", qry(1, n, max(1, b[i].l - b[i].t), b[i].l, 1));
    }
}

int t1[N * 4];

void ubd1(int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        t1[pos] = 1;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd1(tl, m, x, pos * 2);
    else
        ubd1(m + 1, tr, x, pos * 2 + 1);
    t1[pos] = t1[pos * 2] + t1[pos * 2 + 1];
}

int qry1(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t1[pos];
    int m = (tl + tr) / 2;
    return qry1(tl, m, l, min(m, r), pos * 2) +
        qry1(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}

int ans[N];

int u2[N];
vector<int> v[N];
vector<int> q[N];
void solv4()
{
    for (int i = 1; i <= n; ++i)
    {
        u2[i] = u2[i - 1];
        if (s[i] == 2)
            u2[i] = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (u2[i])
            v[i - u2[i]].push_back(i);
    }
    for (int i = 1; i <= m; ++i)
    {
        q[b[i].t].push_back(i);
    }
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            int x = v[i][j];
            ubd1(1, n, x, 1);
        }
        for (int j = 0; j < q[i].size(); ++j)
        {
            int x = q[i][j];
            ans[x] = qry1(1, n, b[x].l, b[x].r, 1) + (b[x].r - b[x].l + 1);
        }
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &s[i]);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &b[i].t, &b[i].l, &b[i].r);
    }
    solv4();
    return 0;
}

Compilation message

ho_t5.cpp: In function 'void solv4()':
ho_t5.cpp:132:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
ho_t5.cpp:137:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < q[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s[i]);
         ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &b[i].t, &b[i].l, &b[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 22264 KB Output is correct
2 Correct 329 ms 22128 KB Output is correct
3 Correct 312 ms 22384 KB Output is correct
4 Correct 317 ms 22400 KB Output is correct
5 Correct 307 ms 22512 KB Output is correct
6 Correct 311 ms 22128 KB Output is correct
7 Correct 311 ms 22292 KB Output is correct
8 Correct 310 ms 22256 KB Output is correct
9 Correct 303 ms 22312 KB Output is correct
10 Correct 307 ms 22196 KB Output is correct
11 Correct 305 ms 22456 KB Output is correct
12 Correct 314 ms 22304 KB Output is correct
13 Correct 301 ms 22320 KB Output is correct
14 Correct 315 ms 22404 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct