Submission #288181

#	Time	Username	Problem	Language	Result	Execution time	Memory
288181		Alexa2001	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	100 / 100	285 ms	22636 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

vector<int> last[Nmax];
int n;
int score1[Nmax], score2[Nmax], id1[Nmax], id2[Nmax];

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

class SegTree
{
    int a[Nmax<<2], lazy[Nmax<<2];

    void propag(int node)
    {
        if(!lazy[node]) return;
        lazy[left_son] += lazy[node];
        lazy[right_son] += lazy[node];
        a[left_son] += lazy[node];
        a[right_son] += lazy[node];
        lazy[node] = 0;
    }

public:
    void update(int node, int st, int dr, int L, int R, int add)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] += add;
            a[node] += add;
            return;
        }

        propag(node);

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

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

    bool good()
    {
        return a[1] >= 0;
    }
} aint;

int solve()
{
    int i, j = 0;
    int matches = 0;

    for(i=1; i<=n; ++i)
    {
        while(j<n && score1[i] <= score2[j+1])
        {
            ++j;
            aint.update(1, 1, n, j, n, +1);
            last[id2[j]].push_back(j);
        }

        if(last[id1[i]].empty())
        {
            aint.update(1, 1, n, j, n, -1);
            continue;
        }

        int pos = last[id1[i]].back();

        aint.update(1, 1, n, pos, n, -1);

        if(aint.good())
        {
            ++matches;
            last[id1[i]].pop_back();
        }
        else
        {
            aint.update(1, 1, n, pos, n, +1);
            aint.update(1, 1, n, j, n, -1);
        }
    }

    return matches;
}

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

    cin >> n;

    int i;
    for(i=1; i<=n; ++i) cin >> id1[i] >> score1[i];
    for(i=1; i<=n; ++i) cin >> id2[i] >> score2[i];

    cout << n - solve() << '\n';

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40