제출 #230014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230014		Vimmer	Sunčanje (COCI18_suncanje)	C++14	130 / 130	2862 ms	94236 KiB

suncanje

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;

typedef short int si;

typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void del(vector <int> &g)
{
    sort(g.begin(), g.end());

    g.resize(unique(g.begin(), g.end()) - g.begin());
}
struct st{

    vector <int> g, fen;

    int kol;

    st() : kol(0), g(0), fen(0) {}

    void build()
    {
        del(g);

        fen.resize(sz(g));
    }

    void upd(int y)
    {
        int v = upper_bound(g.begin(), g.end(), y) - g.begin() - 1;

        for (; v < sz(g); v = (v | (v + 1))) fen[v]++;

        kol++;
    }
    int sm(int y)
    {
        int ans = 0;

        int v = upper_bound(g.begin(), g.end(), y) - g.begin() - 1;

        for (; v >= 0; v = (v & (v + 1)) - 1) ans += fen[v];

        return ans;
    }
};

ordered_set lf, rg, up, dw;

st t[4][N];

vector <int> x1, x2;

int calcer(int x, int y, int xr, int yr)
{
    int kol = 0;

    int v = upper_bound(x2.begin(), x2.end(), x) - x2.begin() - 1;

    for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[0][v].kol - t[0][v].sm(yr - 1);

    v = upper_bound(x2.begin(), x2.end(), x) - x2.begin() - 1;

    for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[2][v].sm(y);

    v = sz(x1) - (lower_bound(x1.begin(), x1.end(), xr) - x1.begin()) - 1;

    for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[1][v].kol - t[1][v].sm(yr - 1);

    v = sz(x1) - (lower_bound(x1.begin(), x1.end(), xr) - x1.begin()) - 1;

    for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[3][v].sm(y);

    return kol;
}

void add(int x, int y, int xr, int yr)
{
    lf.insert(x);

    rg.insert(xr);

    up.insert(yr);

    dw.insert(y);

    int v = lower_bound(x2.begin(), x2.end(), xr) - x2.begin();

    for (; v < sz(x2); v = (v | (v + 1))) t[0][v].upd(y);

    v = lower_bound(x2.begin(), x2.end(), xr) - x2.begin();

    for (; v < sz(x2); v = (v | (v + 1))) t[2][v].upd(yr);

    v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x) - x1.begin()) - 1;

    for (; v < sz(x1); v = (v | (v + 1))) t[1][v].upd(y);

    v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x) - x1.begin()) - 1;

    for (; v < sz(x1); v = (v | (v + 1))) t[3][v].upd(yr);
}

int calc(int x, int y, int xr, int yr)
{
    int kol = 0;

    kol += rg.order_of_key(x + 1);

    kol += up.order_of_key(y + 1);

    kol += sz(lf) - lf.order_of_key(xr);

    kol += sz(dw) - dw.order_of_key(yr);

    return kol;
}

int main()
{
   // freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;

    cin >> n;

    int x[n], y[n], xr[n], yr[n];

    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> xr[i] >> yr[i];

        xr[i] += x[i];

        yr[i] += y[i];

        x1.pb(x[i]);

        x2.pb(xr[i]);
    }

    del(x1); del(x2);

    for (int i = 0; i < n; i++)
    {
        int v = lower_bound(x2.begin(), x2.end(), xr[i]) - x2.begin();

        for (; v < sz(x2); v = (v | (v + 1))) t[0][v].g.pb(y[i]);

        v = lower_bound(x2.begin(), x2.end(), xr[i]) - x2.begin();

        for (; v < sz(x2); v = (v | (v + 1))) t[2][v].g.pb(yr[i]);

        v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x[i]) - x1.begin()) - 1;

        for (; v < sz(x1); v = (v | (v + 1))) t[1][v].g.pb(y[i]);

        v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x[i]) - x1.begin()) - 1;

        for (; v < sz(x1); v = (v | (v + 1))) t[3][v].g.pb(yr[i]);
    }

    for (int i = 0; i < sz(x1); i++) {t[1][i].build(); t[3][i].build();}

    for (int i = 0; i < sz(x2); i++) {t[2][i].build(); t[0][i].build();}

    bool ans[n];

    for (int i = n - 1; i >= 0; i--)
    {
        int cx = x[i], cy = y[i], xc = xr[i], yc = yr[i];

        int kol = calc(cx, cy, xc, yc);

        kol -= calcer(cx, cy, xc, yc);

        ans[i] = (kol == n - i - 1);

        add(cx, cy, xc, yc);
    }

    for (int i = 0; i < n; i++) cout << (ans[i] ? "DA" : "NE") << '\n';
}

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

suncanje.cpp: In constructor 'st::st()':
suncanje.cpp:40:9: warning: 'st::kol' will be initialized after [-Wreorder]
     int kol;
         ^~~
suncanje.cpp:38:18: warning:   'std::vector<int> st::g' [-Wreorder]
     vector <int> g, fen;
                  ^
suncanje.cpp:42:5: warning:   when initialized here [-Wreorder]
     st() : kol(0), g(0), fen(0) {}
     ^~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13