Submission #51748

#	Time	Username	Problem	Language	Result	Execution time	Memory
51748		gs13105	단층 (JOI16_ho_t5)	C++17	100 / 100	303 ms	10948 KiB

2016_ho_t5

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

struct que
{
    int x, d, l;
};

que inp[200010];

long long idx1[525000]; // y + x
long long idx2[525000]; // y - x
int bp;

void add(long long idx[], int x, int y, int v)
{
    if(y < x)
        return;
    x += bp;
    y += bp;
    while(x < y)
    {
        if(x % 2 == 1)
            idx[x++] += v;
        if(y % 2 == 0)
            idx[y--] += v;
        x /= 2;
        y /= 2;
    }
    if(x == y)
        idx[x] += v;
}

long long sum(long long idx[], int x)
{
    long long r = 0;
    x += bp;
    while(x)
    {
        r += idx[x];
        x /= 2;
    }
    return r;
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, q, i;
    scanf("%d%d", &n, &q);
    for(i = 1; i <= q; i++)
        scanf("%d%d%d", &inp[i].x, &inp[i].d, &inp[i].l);

    for(bp = 1; bp <= n; bp *= 2);

    for(i = 1; i <= n; i++)
    {
        add(idx1, i, i, i);
        add(idx2, i, i, -i);
    }

    for(i = q; i >= 1; i--)
    {
        if(inp[i].d == 1)
        {
            int s = 0;
            int g = n;
            while(s < g)
            {
                int x = (s + g + 1) / 2;
                if(sum(idx2, x) + inp[i].x >= 0)
                    s = x;
                else
                    g = x - 1;
            }
            add(idx1, 1, s, -2 * inp[i].l);
        }
        else
        {
            int s = 1;
            int g = n + 1;
            while(s < g)
            {
                int x = (s + g) / 2;
                if(sum(idx1, x) - inp[i].x - 1 >= 0)
                    g = x;
                else
                    s = x + 1;
            }
            add(idx2, s, n, -2 * inp[i].l);
        }
    }

    for(i = 1; i <= n; i++)
    {
        long long r = -(sum(idx1, i) + sum(idx2, i)) / 2;
        printf("%lld\n", r);
    }
    return 0;
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t5.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &inp[i].x, &inp[i].d, &inp[i].l);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66