QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#398056#8179. 2D Parenthesesperekopska_dWA 364ms103084kbC++145.6kb2024-04-24 21:37:132024-04-24 21:37:16

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 21:37:16]
  • 评测
  • 测评结果:WA
  • 用时:364ms
  • 内存:103084kb
  • [2024-04-24 21:37:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ff first
#define ss second
#define pii pair <int, int>
#define el '\n'
#define pb push_back
#define mkp make_pair

const ll inf = 1e9 + 10;
const ll N = 2e5 + 50;
const ll LOG = 22;
const ll mod = 998244353;

struct pp {
    int x;
    int y;
    bool f;
    int id;
};

struct seg {
    int y;
    int l;
    int r;
    bool f;
};

int n, m, m2;
pp b[2 * N], a[2 * N];
multiset <int> st1[2 * N], st2[2 * N];
int ans[N], t1[8 * N], t2[8 * N];
vector <seg> v1, v2;
vector <int> xx, yy;
map <int, int> pos, pos2;

void full() {
    for(int i = 0; i < 8 * N; i++) {
        t1[i] = inf;
        t2[i] = -inf;
    }
}

bool comp(pp a, pp b) {
    if(a.y != b.y) return a.y < b.y;
    return a.x > b.x;
}

bool comp2(seg a, seg b) {
    if(a.y != b.y) return a.y < b.y;
    return a.f < b.f;
}

int get1(int i, int tl, int tr, int l, int r) {
    if(tr < l || r < tl) return inf;
    if(l <= tl && tr <= r) return t1[i];

    int mid = (tl + tr) / 2;
    return min(get1(i + i, tl, mid, l, r), get1(i + i + 1, mid + 1, tr, l, r));
}

int get2(int i, int tl, int tr, int l, int r) {
    if(tr < l || r < tl) return -inf;
    if(l <= tl && tr <= r) return t2[i];

    int mid = (tl + tr) / 2;
    return max(get2(i + i, tl, mid, l, r), get2(i + i + 1, mid + 1, tr, l, r));
}

void update1(int i, int tl, int tr, int pos, int val, int f) {
    if(tl == tr) {
        if(f) st1[tl].insert(val);
        else st1[tl].erase(val);

        if(st1[tl].size()) t1[i] = *st1[tl].begin();
        else t1[i] = inf;
        return;
    }
    int mid = (tl + tr) / 2;
    if(pos <= mid) update1(i + i, tl, mid, pos, val, f);
    else update1(i + i + 1, mid + 1, tr, pos, val, f);
    t1[i] = min(t1[i + i], t1[i + i + 1]);
}

void update2(int i, int tl, int tr, int pos, int val, int f) {
    if(tl == tr) {
        if(f) st2[tl].insert(val);
        else st2[tl].erase(val);

        if(st2[tl].size()) {
            auto it = st2[tl].end(); it--;
            t2[i] = *it;
        }
        else t2[i] = -inf;
        return;
    }
    int mid = (tl + tr) / 2;
    if(pos <= mid) update2(i + i, tl, mid, pos, val, f);
    else update2(i + i + 1, mid + 1, tr, pos, val, f);
    t2[i] = max(t2[i + i], t2[i + i + 1]);
}

bool check_x(seg s) {
    int r = lower_bound(xx.begin(), xx.end(), s.r) - xx.begin() - 1;
    r = pos[xx[r]];
    int l = upper_bound(xx.begin(), xx.end(), s.l) - xx.begin();
    l = pos[xx[l]];

    if(l > r) return 0;
    if(get1(1, 1, m, l, r) < s.l) return 1;
    if(get2(1, 1, m, l, r) > s.r) return 1;
    return 0;
}

bool check_y(seg s) {
    int r = lower_bound(yy.begin(), yy.end(), s.r) - yy.begin() - 1;
    r = pos2[yy[r]];
    int l = upper_bound(yy.begin(), yy.end(), s.l) - yy.begin();
    l = pos2[yy[l]];

    if(l > r) return 0;
    if(get1(1, 1, m2, l, r) < s.l) return 1;
    if(get2(1, 1, m2, l, r) > s.r) return 1;
    return 0;
}

void upd_x(seg s) {
    int i = pos[s.r];
    update1(1, 1, m, i, s.l, s.f);
    i = pos[s.l];
    update2(1, 1, m, i, s.r, s.f);
}

void upd_y(seg s) {
    int i = pos2[s.r];
    update1(1, 1, m2, i, s.l, s.f);
    i = pos2[s.l];
    update2(1, 1, m2, i, s.r, s.f);
}

void solve() {
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> b[i].x >> b[i].y;
        b[i].f = 1;
        b[i].id = i;
        xx.pb(b[i].x);
        yy.pb(b[i].y);
    }

    for(int i = n; i < n + n; i++) {
        cin >> b[i].x >> b[i].y;
        b[i].f = 0;
        b[i].id = i;
        xx.pb(b[i].x);
        yy.pb(b[i].y);
    }

    sort(xx.begin(), xx.end());
    sort(yy.begin(), yy.end());

    int cur = 1;
    for(int i = 0; i < n + n; i++) {
        if(i && xx[i - 1] != xx[i]) cur++;
        pos[xx[i]] = cur;
        m = cur;
    }
    cur = 1;
    for(int i = 0; i < n + n; i++) {
        if(i && yy[i - 1] != yy[i]) cur++;
        pos2[yy[i]] = cur;
        m2 = cur;
    }

    for(int i = 0; i < n + n; i++)
        a[i] = b[i];
    sort(a, a + n + n, comp);

    set <pii> st;
    for(int i = 0; i < n + n; i++) {
        if(a[i].f) st.insert({a[i].x, a[i].id});
        else {
            auto it = st.lower_bound(mkp(a[i].x, 0));
            if(it == st.begin()) return void(cout << "No");
            it--;
            pii j = *it; st.erase(it);
            ans[j.ss] = a[i].id - n + 1;

            v1.pb({b[j.ss].y, j.ff, a[i].x, 1});
            v1.pb({a[i].y, j.ff, a[i].x, 0});

            v2.pb({j.ff, b[j.ss].y, a[i].y, 1});
            v2.pb({a[i].x, b[j.ss].y, a[i].y, 0});
        }
    }

    sort(v1.begin(), v1.end(), comp2);
    sort(v2.begin(), v2.end(), comp2);

    full();
    for(int i = 0; i < n + n; i++) {
        int j = i;
        while(j < n + n && v1[j].y == v1[i].y && !v1[j].f)
            upd_x(v1[j]), j++;
        while(j < n + n && v1[j].y == v1[i].y) {
            if(check_x(v1[j])) return void(cout << "No");
            upd_x(v1[j]); j++;
        }
        i = j - 1;
    }

    full();
    for(int i = 0; i < n + n; i++) {
        int j = i;
        while(j < n + n && v2[j].y == v2[i].y && !v2[j].f)
            upd_y(v2[j]), j++;
        while(j < n + n && v2[j].y == v2[i].y) {
            if(check_y(v2[j])) return void(cout << "No");
            upd_y(v2[j]); j++;
        }
        i = j - 1;
    }

    cout << "Yes" << el;
    for(int i = 0; i < n; i++)
        cout << ans[i] << el;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 53900kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

Yes
3
2
1

result:

ok answer is YES, 3 tokens

Test #2:

score: 0
Accepted
time: 4ms
memory: 53596kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 11ms
memory: 41032kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 364ms
memory: 103084kb

input:

199996
94702923 895749121
-830347683 823853414
-638337012 -528381915
774504965 -903560893
465975432 931026841
47062323 901390864
539345338 830099354
278774201 896803047
-445303873 568413124
80473317 828648317
804283391 -307873779
543648687 893783688
814084625 -664894626
169476937 -999435847
-8232728...

output:

No

result:

wrong answer expected YES, found NO