제출 #1325961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325961		goldenbull	Examination (JOI19_examination)	C++17	100 / 100	383 ms	18212 KiB

examination

#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FOD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define FF(i,a,b,c) for (int i=(a),_b=(b),_c=(c); i<=_b; i+=_c)
#define FFD(i,a,b,c) for (int i=(a),_b=(b),_c=(c); i>=_b; i-=_c)
#define FUL(n) (((1LL)<<(n))-1)
#define BIT(n,k) (((n)>>(k))&1)
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define sqr(x) (1LL * (x) * (x))
#define lsb(x) ((1LL*x) & (-1LL*x))
using namespace std;
using ll = long long;
using ull = uint64_t;
using ld = long double;
template<class T> using ve = vector<T>;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll,ll>;
const char el = '\n';
template<class T, class U> bool maxi(T& x, const U& y) { return y>x?(x=y,1):0; }
template<class T, class U> bool mini(T& x, const U& y) { return y<x?(x=y,1):0; }
static int tc = 1;
static int _case = 1;

const int N = 2e5+7;

struct pt {
    int x,y,z,id;
    bool operator<(const pt &oth) const {
        if (x != oth.x) return x > oth.x;
        else if (y != oth.y) return y > oth.y;
        else if (z != oth.z) return z > oth.z;
        return id < oth.id;
    }
};

struct FW {
    int n;
    vi ar;
    void init(int _n) {
        n = _n;
        ar.assign(n+1,0);
    }
    void upd(int i, int delt) {
        for (;i;i-=lsb(i)) ar[i] += delt;
    }
    int get(int i) {
        int ans=0;
        for (;i<=n;i+=lsb(i)) ans += ar[i];
        return ans;
    }
};

int n,q,add[N],sub[N];
vi cp;
pt a[N];
FW idk;

void cdq(int l, int r, int ans[]) {
    if (l>=r) return;

    int m = l+r>>1;
    cdq(l,m,ans); cdq(m+1,r,ans);

    ve<pt> tmp, del;
    int p1=l, p2=m+1;
    while (p1<=m && p2<=r) {
        if (a[p1].y >= a[p2].y) {
            idk.upd(a[p1].z,1);
            del.pb(a[p1]);
            tmp.pb(a[p1++]);
        }
        else {
            ans[a[p2].id] += idk.get(a[p2].z);
            tmp.pb(a[p2++]);
        }
    }
    while (p1<=m) tmp.pb(a[p1++]);
    while (p2<=r) {
        ans[a[p2].id] += idk.get(a[p2].z);
        tmp.pb(a[p2++]);
    }

    FOR(i,l,r) a[i] = tmp[i-l];
    for (auto i:del) idk.upd(i.z,-1);
}

int po(int k) { return lower_bound(all(cp),k) - cp.begin() + 1; }
void compress() {
    FOR(i,1,n) cp.pb(a[i].x), cp.pb(a[i].y), cp.pb(a[i].z);
    sort(all(cp)); cp.resize(unique(all(cp))-cp.begin());
    FOR(i,1,n) a[i] = {po(a[i].x), po(a[i].y), po(a[i].z), a[i].id};
}

void solve() {
    cin>>n>>q;
    FOR(i,1,n){
        int x,y; cin>>x>>y;
        a[i] = {x,y,x+y,i};
    }
    FOR(i,1,q) {
        int x,y,z; cin>>x>>y>>z;
        a[n+i] = {x,y,z,n+i};
    }
    n += q;

    compress();
    idk.init(sz(cp)+5);

    sort(a+(n-q)+1,a+n+1);
    cdq(n-q+1,n,sub);

    sort(a+1,a+n+1);
    cdq(1,n,add);

    FOR(i,n-q+1,n) cout << add[i] - sub[i] << el;

    /// debug
//    cerr << el;
//    FOR(i,1,n) cerr << a[i].x << ' ' << a[i].y << ' ' << a[i].z << ' ' << a[i].id << el;
//    FOR(i,1,n) cerr << sub[i] << ' '; cerr << el;
//    FOR(i,1,n) cerr << add[i] << ' '; cerr << el;
}

#define IN ".inp"
#define OUT ".out"
//#define NAME "test"
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifndef NAME
        if (fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
    #endif
    #ifdef NAME
        freopen(NAME IN, "r", stdin);
        freopen(NAME OUT, "w", stdout);
    #endif
    // cin>>tc;
    while (tc--) solve();
    cerr << el << "Time elapsed: " << TIME << " s";
    return 0;
}

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

examination.cpp: In function 'int main()':
examination.cpp:137:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         if (fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57