oj.uz

Submission #210049

# Submission time Handle Problem Language Result Execution time Memory
210049 2020-03-16T13:12:55 Z Alexa2001 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 205396 KB 
#include <bits/stdc++.h>

using namespace std;

const int lim = 2e8+2, Nmax = 3e5 + 5, Lim = 2 * Nmax;
typedef pair<int,int> Pair;


int n, k, q;
int x[Nmax], tip[Nmax], start[Nmax], finish[Nmax], ans[Nmax];
int X[Nmax], T[Nmax];

vector<Pair> v[Nmax];

vector<int> ord;

struct modif
{
    int tmp, l, r, add;
};
vector<modif> op;

auto inv_sort = [](Pair a, Pair b) { return a > b; };



#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


class SegmentTree
{
    vector<Pair> o;
    int n;
    int a[Lim<<2];
    map<Pair, int> In, Out;

    void update(int node, int st, int dr, int pos, int add)
    {
        if(st == dr)
        {
            if(add == 1) a[node] = o[pos].second;
                else a[node] = (1<<30);
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos, add);
            else update(right_son, mid+1, dr, pos, add);

        a[node] = min(a[left_son], a[right_son]);
    }

    int query(int node, int st, int dr, int pos)
    {
        if(o[st].first < pos) return (1<<30);
        if(o[dr].first >= pos) return a[node];

        int res1 = query(left_son, st, mid, pos),
            res2 = query(right_son, mid+1, dr, pos);
        return min(res1, res2);
    }

public:
    void init(vector<Pair> &all)
    {
        o = all;
        n = all.size();
        memset(a, 0x3f3f3f3f, sizeof(a));
    }

    void update(modif el)
    {
        int pos;
        if(el.add == 1)
        {
            int nr = In[{el.r, el.l}]++;
            pos = lower_bound(o.begin(), o.end(), make_pair(el.r, el.l), inv_sort) - o.begin() + nr;
        }
        else
        {
            int nr = Out[{el.r, el.l}]++;
            pos = lower_bound(o.begin(), o.end(), make_pair(el.r, el.l), inv_sort) - o.begin() + nr;
        }

        update(1, 0, n-1, pos, el.add);
    }

    int query(int pos)
    {
        return pos - query(1, 0, n-1, pos);
    }
} aint;



void find_segments()
{
    int i;
    for(i=1; i<=n; ++i)
    {
        v[tip[i]].push_back({start[i], +x[i]});
        v[tip[i]].push_back({finish[i]+1, -x[i]});
    }

    for(i=1; i<=k; ++i)
    {
        sort(v[i].begin(), v[i].end());

        multiset<int> S;

        S.insert(-4*lim);
        S.insert(2*lim);

        op.push_back({0, -4*lim, 2*lim});

        for(auto el : v[i])
            if(el.second > 0) /// insert new store
            {
                int X = el.second;
                multiset<int> :: iterator it = S.insert(X);
                int X1, X2;

                X1 = *prev(it);
                X2 = *next(it);

                op.push_back({el.first, X1, (X1 + X2) / 2, -1});
                op.push_back({el.first, X1, (X1 + X) / 2, +1});
                op.push_back({el.first, X, (X + X2) / 2, +1});
            }
            else
            {
                int X = -el.second;
                multiset<int> :: iterator it = S.find(X);
                int X1, X2;

                X1 = *prev(it);
                X2 = *next(it);

                S.erase(it);

                op.push_back({el.first, X1, (X1 + X2) / 2, +1});
                op.push_back({el.first, X1, (X1 + X) / 2, -1});
                op.push_back({el.first, X, (X + X2) / 2, -1});
            }
    }
}


void prepare()
{
    vector<Pair> all;
    for(auto it : op)
        if(it.add == 1)
            all.push_back({ it.r, it.l });

    sort(all.begin(), all.end(), inv_sort);
    aint.init(all);
}

vector<int> sort_queries()
{
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [](int x, int y) { return T[x] < T[y]; });
    return ord;
}

void sort_op()
{
    sort(op.begin(), op.end(), [](modif a, modif b) { return a.tmp < b.tmp; });
}


void change(int &x, int y)
{
    if(x == -1) return;
    if(x < y) x = y;
}

void solve_queries(vector<int> &ord)
{
    int p = 0;
    for(auto id : ord)
    {
        while(p<op.size() && op[p].tmp <= T[id])
            aint.update(op[p]), p++;

        change(ans[id], aint.query(X[id]) / 2);
    }
}

void solve()
{
    find_segments();
    prepare();
    sort_op();
    solve_queries(ord);
}

void clr()
{
    int i;
    for(i=1; i<=k; ++i) v[i].clear();
    op.clear();
}

void prec()
{
    int i;
    vector<Pair> V;
    for(i=1; i<=n; ++i)
    {
        V.push_back({ start[i], tip[i] });
        V.push_back({ finish[i]+1, -tip[i] });
    }

    sort(V.begin(), V.end());

    i = 0;
    int nr_dif = 0;
    vector<int> cnt(k+1,0);

    for(auto id : ord)
    {
        while(i < V.size() && V[i].first <= T[id])
        {
            if(V[i].second > 0)
            {
                ++cnt[V[i].second];
                if(cnt[V[i].second] == 1) ++nr_dif;
            }
            else
            {
                --cnt[-V[i].second];
                if(cnt[-V[i].second] == 0) --nr_dif;
            }
            ++i;
        }
        if(nr_dif < k) ans[id] = -1;
    }
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> k >> q;

    int i;
    for(i=1; i<=n; ++i) cin >> x[i] >> tip[i] >> start[i] >> finish[i];
    for(i=1; i<=q; ++i) cin >> X[i] >> T[i];

    for(i=1; i<=n; ++i) x[i] *= 2;
    for(i=1; i<=q; ++i) X[i] *= 2;

    ord = sort_queries();

    prec();

    solve();
    clr();

    for(i=1; i<=n; ++i) x[i] = lim - x[i];
    for(i=1; i<=q; ++i) X[i] = lim - X[i];

    solve();

    for(i=1; i<=q; ++i)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message

new_home.cpp: In function 'void solve_queries(std::vector<int>&)':
new_home.cpp:186:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p<op.size() && op[p].tmp <= T[id])
               ~^~~~~~~~~~
new_home.cpp: In function 'void prec()':
new_home.cpp:226:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < V.size() && V[i].first <= T[id])
               ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 15 ms 16760 KB Output is correct
4 Correct 15 ms 16760 KB Output is correct
5 Incorrect 17 ms 16888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 15 ms 16760 KB Output is correct
4 Correct 15 ms 16760 KB Output is correct
5 Incorrect 17 ms 16888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 15 ms 16760 KB Output is correct
4 Correct 15 ms 16760 KB Output is correct
5 Incorrect 17 ms 16888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 16 ms 16760 KB Output is correct
3 Correct 15 ms 16760 KB Output is correct
4 Correct 15 ms 16760 KB Output is correct
5 Incorrect 17 ms 16888 KB Output isn't correct
6 Halted 0 ms 0 KB -