oj.uz

Submission #234446

# Submission time Handle Problem Language Result Execution time Memory
234446 2020-05-24T09:01:25 Z Vimmer Plahte (COCI17_plahte) C++14
0 / 160
 2000 ms 42476 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200005
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;

typedef long double ld;
typedef long long ll;

typedef short int si;



vector <int> X;

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

    v.resize(unique(v.begin(), v.end()) - v.begin());
}

struct st{

    vector <int> g, fn;

    st() : g(0), fn(0) {}

    void upd(int y)
    {
        y = lower_bound(g.begin(), g.end(), y) - g.begin();

        for (; y < sz(g); y = (y | (y + 1))) fn[y]++;
    }

    void updr(int y)
    {
        y = lower_bound(g.begin(), g.end(), y) - g.begin();

        for (; y < sz(g); y = (y | (y + 1))) fn[y]++;
    }

    void bld()
    {
        del(g);

        fn.resize(sz(g));
    }

    int sm(int y)
    {
        int ans = 0;

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

        for (; y >= 0; y = (y & (y + 1)) - 1) ans += fn[y];

        return ans;
    }
};

st t[N];

vector <pair <int, int> > kr[N];

int calc(int xl, int yl, int xr, int yr)
{
    int ans = 0;

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

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

    v = upper_bound(X.begin(), X.end(), xl - 1) - X.begin() - 1;

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

    v = upper_bound(X.begin(), X.end(), xl - 1) - X.begin() - 1;

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

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

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

    return ans;
}

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, q;

    cin >> n >> q;

    int xl[n], yl[n], xr[n], yr[n];

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

        X.pb(xl[i]);

        X.pb(xr[i]);
    }

    vector <int> g; g.clear();

    int x[q], y[q], c[q];

    for (int i = 0; i < q; i++)
    {
        cin >> x[i] >> y[i] >> c[i];

        X.pb(x[i]);

        kr[c[i]].pb({x[i], y[i]});

        if (sz(kr[c[i]]) == 2) g.pb(c[i]);
    }

    X.pb(-1e9);

    X.pb(1e9 + 1e9);

    del(X);

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

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

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

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

    for (int i = 0; i < q; i++)
    {
        int v = lower_bound(X.begin(), X.end(), x[i]) - X.begin();

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

    for (int i = 0; i < sz(X); i++) t[i].bld();

    for (int i = 0; i < q; i++)
    {
        int v = lower_bound(X.begin(), X.end(), x[i]) - X.begin();

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

    for (int i = 0; i < n; i++)
    {
        int ans = calc(xl[i], yl[i], xr[i], yr[i]), mns = 0;

        for (auto it : g)
        {
            for (auto itr : kr[it])
            {
                int v = lower_bound(X.begin(), X.end(), itr.F) - X.begin();

                for (; v < sz(X); v = (v | (v + 1))) t[v].upd(itr.S);
            }

            int nw = calc(xl[i], yl[i], xr[i], yr[i]) - mns;

            int ost = nw - ans - 1;

            mns += ost;

            ans -= ost;

            for (auto itr : kr[it])
            {
                int v = lower_bound(X.begin(), X.end(), itr.F) - X.begin();

                for (; v < sz(X); v = (v | (v + 1))) t[v].updr(itr.S);
            }
        }

        cout << ans << '\n';
    }
}

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2098 ms 27120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 30452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 42476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 38252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 38252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -