제출 #777647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777647		hgmhc	단층 (JOI16_ho_t5)	C++17	100 / 100	152 ms	13336 KiB

2016_ho_t5

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

template <const int N>
struct seg {
    ll t[2*N]{};
    void update(int a, int b, ll v) {
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) t[a] += v;
            if (~b&1) t[b] += v;
        }
    }
    ll query(int k) {
        ll r = 0;
        for (k += N; k >= 1; k /= 2) r += t[k];
        return r;
    }
};

const int N = 2e5+3, Q = N;
int n, q;
seg<N> x, y;
int a[N], b[N], c[N];

int main() {
    scanf("%d%d", &n, &q);
    rep(i,1,q) scanf("%d%d%d", &a[i], &b[i], &c[i]);
    rep(i,0,n-1) x.t[N+i] = i+1, y.t[N+i] = i;
    per(i,1,q) {
        if (b[i] == 1) {
            // x좌표가 a[i] 미만인 애들 y좌표 c[i]만큼 감소
            ll l = 0, u = n-1, m;
            while (l <= u) {
                m = (l+u)/2;
                if (x.query(m) <= a[i]) l = m+1;
                else u = m-1;
            }
            y.update(0,u,-2*c[i]);
        } else {
            // y좌표가 a[i] 이상인 애들 x좌표 c[i]만큼 증가
            ll l = 0, u = n-1, m;
            while (l <= u) {
                m = (l+u)/2;
                if (y.query(m) >= a[i]) u = m-1;
                else l = m+1;
            }
            x.update(l,n-1,+2*c[i]);
        }
    }
    rep(i,0,n-1) {
        printf("%lld\n", (x.query(i)-y.query(i))/2);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t5.cpp:36:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     rep(i,1,q) scanf("%d%d%d", &a[i], &b[i], &c[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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