답안 #57146 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57146	2018-07-14T07:06:36 Z	gs13105	Employment (JOI16_employment)	C++17	100 / 100	655 ms	124732 KB

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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	528 KB	Output is correct
3	Correct	2 ms	644 KB	Output is correct
4	Correct	5 ms	808 KB	Output is correct
5	Correct	3 ms	808 KB	Output is correct
6	Correct	4 ms	808 KB	Output is correct
7	Correct	6 ms	940 KB	Output is correct
8	Correct	5 ms	988 KB	Output is correct
9	Correct	5 ms	1000 KB	Output is correct
10	Correct	6 ms	1120 KB	Output is correct
11	Correct	7 ms	1244 KB	Output is correct
12	Correct	7 ms	1292 KB	Output is correct
13	Correct	7 ms	1468 KB	Output is correct
14	Correct	7 ms	1468 KB	Output is correct
15	Correct	7 ms	1468 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1500 KB	Output is correct
2	Correct	6 ms	1520 KB	Output is correct
3	Correct	5 ms	1552 KB	Output is correct
4	Correct	26 ms	2628 KB	Output is correct
5	Correct	45 ms	3988 KB	Output is correct
6	Correct	70 ms	5872 KB	Output is correct
7	Correct	144 ms	8688 KB	Output is correct
8	Correct	167 ms	11512 KB	Output is correct
9	Correct	301 ms	17848 KB	Output is correct
10	Correct	267 ms	19580 KB	Output is correct
11	Correct	423 ms	25392 KB	Output is correct
12	Correct	392 ms	30536 KB	Output is correct
13	Correct	368 ms	34620 KB	Output is correct
14	Correct	323 ms	38640 KB	Output is correct
15	Correct	378 ms	42828 KB	Output is correct
16	Correct	363 ms	47276 KB	Output is correct
17	Correct	448 ms	51608 KB	Output is correct
18	Correct	432 ms	55876 KB	Output is correct
19	Correct	436 ms	60280 KB	Output is correct
20	Correct	362 ms	64460 KB	Output is correct

Subtask #3
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	528 KB	Output is correct
3	Correct	2 ms	644 KB	Output is correct
4	Correct	5 ms	808 KB	Output is correct
5	Correct	3 ms	808 KB	Output is correct
6	Correct	4 ms	808 KB	Output is correct
7	Correct	6 ms	940 KB	Output is correct
8	Correct	5 ms	988 KB	Output is correct
9	Correct	5 ms	1000 KB	Output is correct
10	Correct	6 ms	1120 KB	Output is correct
11	Correct	7 ms	1244 KB	Output is correct
12	Correct	7 ms	1292 KB	Output is correct
13	Correct	7 ms	1468 KB	Output is correct
14	Correct	7 ms	1468 KB	Output is correct
15	Correct	7 ms	1468 KB	Output is correct
16	Correct	4 ms	1500 KB	Output is correct
17	Correct	6 ms	1520 KB	Output is correct
18	Correct	5 ms	1552 KB	Output is correct
19	Correct	26 ms	2628 KB	Output is correct
20	Correct	45 ms	3988 KB	Output is correct
21	Correct	70 ms	5872 KB	Output is correct
22	Correct	144 ms	8688 KB	Output is correct
23	Correct	167 ms	11512 KB	Output is correct
24	Correct	301 ms	17848 KB	Output is correct
25	Correct	267 ms	19580 KB	Output is correct
26	Correct	423 ms	25392 KB	Output is correct
27	Correct	392 ms	30536 KB	Output is correct
28	Correct	368 ms	34620 KB	Output is correct
29	Correct	323 ms	38640 KB	Output is correct
30	Correct	378 ms	42828 KB	Output is correct
31	Correct	363 ms	47276 KB	Output is correct
32	Correct	448 ms	51608 KB	Output is correct
33	Correct	432 ms	55876 KB	Output is correct
34	Correct	436 ms	60280 KB	Output is correct
35	Correct	362 ms	64460 KB	Output is correct
36	Correct	4 ms	64460 KB	Output is correct
37	Correct	6 ms	64460 KB	Output is correct
38	Correct	7 ms	64460 KB	Output is correct
39	Correct	37 ms	64460 KB	Output is correct
40	Correct	59 ms	64460 KB	Output is correct
41	Correct	138 ms	64460 KB	Output is correct
42	Correct	192 ms	64460 KB	Output is correct
43	Correct	281 ms	65552 KB	Output is correct
44	Correct	539 ms	72608 KB	Output is correct
45	Correct	411 ms	74748 KB	Output is correct
46	Correct	418 ms	78924 KB	Output is correct
47	Correct	595 ms	85760 KB	Output is correct
48	Correct	590 ms	90588 KB	Output is correct
49	Correct	561 ms	95380 KB	Output is correct
50	Correct	521 ms	100068 KB	Output is correct
51	Correct	655 ms	105296 KB	Output is correct
52	Correct	579 ms	110020 KB	Output is correct
53	Correct	633 ms	115072 KB	Output is correct
54	Correct	534 ms	119924 KB	Output is correct
55	Correct	634 ms	124732 KB	Output is correct

답안 #57146

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 30.0 / 30.0

Subtask #3 60.0 / 60.0

Subtask #1
10.0 / 10.0

Subtask #2
30.0 / 30.0

Subtask #3
60.0 / 60.0