Submission #57146

#	Time	Username	Problem	Language	Result	Execution time	Memory
57146		gs13105	Employment (JOI16_employment)	C++17	100 / 100	655 ms	124732 KiB

employment

#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;
 
int idx[1050000];
int bp;
 
void add(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;
}
 
int sum(int x)
{
    int r = 0;
    x += bp;
    while(x)
    {
        r += idx[x];
        x /= 2;
    }
    return r;
}
 
int arr[200010];
int que[200010][3];
 
vector<int> com;
inline int cnv(int x)
{
    return lower_bound(com.begin(), com.end(), x) - com.begin();
}
 
int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
 
    int n, m, i, j;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < 2; j++)
            scanf("%d", &que[i][j]);
        if(que[i][0] == 2)
            scanf("%d", &que[i][2]);
    }
 
    for(i = 0; i <= n; i++)
        com.push_back(arr[i]);
    for(i = 0; i < m; i++)
    {
        if(que[i][0] == 1)
            com.push_back(que[i][1]);
        else
            com.push_back(que[i][2]);
    }
 
    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
 
    for(bp = 1; bp < com.size(); bp *= 2);
 
    for(i = 0; i < n; i++)
        add(cnv(arr[i]) + 1, cnv(arr[i + 1]), 1);
 
    for(i = 0; i < m; i++)
    {
        if(que[i][0] == 1)
        {
            int r = sum(cnv(que[i][1]));
            printf("%d\n", r);
        }
        else
        {
            int x = que[i][1];
 
            add(cnv(arr[x - 1]) + 1, cnv(arr[x]), -1);
            add(cnv(arr[x]) + 1, cnv(arr[x + 1]), -1);
 
            arr[x] = que[i][2];
 
            add(cnv(arr[x - 1]) + 1, cnv(arr[x]), 1);
            add(cnv(arr[x]) + 1, cnv(arr[x + 1]), 1);
        }
    }
    return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(bp = 1; bp < com.size(); bp *= 2);
                 ~~~^~~~~~~~~~~~
employment.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
employment.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &que[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~
employment.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &que[i][2]);
             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60