oj.uz

답안 #144509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144509 2019-08-17T01:20:56 Z arnold518 Employment (JOI16_employment) C++14
30 / 100
 506 ms 16564 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXVAL = 4e5;
const int INF = 2147483647;

struct Data { int t, a, b; };

int N, Q, A[MAXN+10];
Data B[MAXN+10];
int tree[4*MAXVAL+10];
vector<int> comp, comp2;

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }
int getcomp2(int x) { return *lower_bound(comp2.begin(), comp2.end(), x); }

void update(int node, int tl, int tr, int l, int r, int val)
{
	if(l>r) return;
	if(tr<l || r<tl) return;
	if(l<=tl && tr<=r)
	{
        tree[node]+=val;
        return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, val);
	update(node*2+1, mid+1, tr, l, r, val);
}

int query(int node, int tl, int tr, int pos)
{
	if(tl==tr) return tree[node];
	int mid=tl+tr>>1;
	if(pos<=mid) return tree[node]+query(node*2, tl, mid, pos);
	else return tree[node]+query(node*2+1, mid+1, tr, pos);
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
    for(i=1; i<=Q; i++)
    {
    	scanf("%d", &B[i].t);
    	if(B[i].t==1) scanf("%d", &B[i].a);
    	else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
    }
    comp.push_back(INF); comp.push_back(1); comp2.push_back(INF); comp2.push_back(0);
    sort(comp.begin(), comp.end()); sort(comp2.begin(), comp2.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end()); comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());

    for(i=1; i<=N+1; i++)
    {
    	int a=min(A[i], A[i-1])+1, b=max(A[i], A[i-1]);
    	update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
    }

    for(i=1; i<=Q; i++)
    {
        if(B[i].t==1) printf("%d\n", query(1, 1, comp.size(), getcomp(getcomp2(B[i].a)))/2);
        else
        {
            int a, b;
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
            a=min(A[B[i].a], A[B[i].a+1])+1, b=max(A[B[i].a], A[B[i].a+1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
            A[B[i].a]=B[i].b;
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
            a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
            update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
        }
    }
}

Compilation message

employment.cpp: In function 'void update(int, int, int, int, int, int)':
employment.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int query(int, int, int, int)':
employment.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int main()':
employment.cpp:46:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
employment.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:49:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:52:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &B[i].t);
      ~~~~~^~~~~~~~~~~~~~~
employment.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      if(B[i].t==1) scanf("%d", &B[i].a);
                    ~~~~~^~~~~~~~~~~~~~~
employment.cpp:54:92: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 28 ms 1564 KB Output is correct
5 Correct 63 ms 3312 KB Output is correct
6 Correct 89 ms 4208 KB Output is correct
7 Correct 161 ms 7148 KB Output is correct
8 Correct 194 ms 7916 KB Output is correct
9 Correct 332 ms 11320 KB Output is correct
10 Correct 346 ms 13412 KB Output is correct
11 Correct 395 ms 15208 KB Output is correct
12 Correct 457 ms 16220 KB Output is correct
13 Correct 471 ms 16228 KB Output is correct
14 Correct 451 ms 16104 KB Output is correct
15 Correct 463 ms 16356 KB Output is correct
16 Correct 506 ms 16392 KB Output is correct
17 Correct 488 ms 16400 KB Output is correct
18 Correct 494 ms 16416 KB Output is correct
19 Correct 456 ms 16488 KB Output is correct
20 Correct 453 ms 16564 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -