QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61400#4236. Triangular Logs2pal1rak#WA 2ms25948kbC++143.6kb2022-11-12 20:30:212022-11-12 20:30:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 20:30:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:25948kb
  • [2022-11-12 20:30:21]
  • 提交

answer

#include <bits/stdc++.h>

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


using namespace std;

const int Nmax = 1e5 + 5;
const int threshold = 50;

struct tree
{
    int x, y, h;
} a[Nmax];

struct query
{
    int xl, xh, yl, yh;
    vector<int> v;
} b[Nmax];

vector<int> unique_xs, unique_ys;
map<int,int> xs, ys;


int currX;

int n, q, lim;

vector<pair<int, pair<int,int>>> events;



void normalize()
{
    int i;

    int nr = 0;
    for(auto &it : ys)
    {
        it.second = ++nr;
        unique_ys.push_back(it.first);
    }

    nr = 0;
    for(auto &it : xs)
    {
        it.second = ++nr;
        unique_xs.push_back(it.first);
    }

    for(i=1; i<=n; ++i)
    {
        a[i].x = xs[a[i].x];
        a[i].y = ys[a[i].y];
    }

    for(i=1; i<=q; ++i)
    {
        b[i].xl = lower_bound(unique_xs.begin(), unique_xs.end(), b[i].xl) - unique_xs.begin() + 1;
        b[i].xh = upper_bound(unique_xs.begin(), unique_xs.end(), b[i].xh) - unique_xs.begin();

        b[i].yl = lower_bound(unique_ys.begin(), unique_ys.end(), b[i].yl) - unique_ys.begin() + 1;
        b[i].yh = upper_bound(unique_ys.begin(), unique_ys.end(), b[i].yh) - unique_ys.begin();
    }
}


class SegTree
{
    vector<int> queries[Nmax<<3];


    void do_update(vector<int> &v, int val)
    {
        vector<int> vv;
        for(auto id : v)
            if(currX <= b[id].xh) // still good
            {
                b[id].v.push_back(val);
                if(b[id].v.size() < threshold)
                {
                    vv.push_back(id);
                }
            }
        v = vv;
    }

public:
    void add(int node, int st, int dr, int L, int R, int id)
    {
        if(st <= L && R <= dr)
        {
            queries[node].push_back(id);
            return;
        }

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

    void update(int node, int st, int dr, int pos, int val)
    {
        do_update(queries[node], val);

        if(st == dr) return;

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






bool get_result(vector<int> &v)
{
    if(v.size() >= threshold) return 1;
    sort(v.begin(), v.end());

    int i;
    for(i=0; i+2 < v.size(); ++i)
        if(v[i] + v[i+1] > v[i+2]) return 1;

    return 0;
}

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

    cin >> n >> q;

    int i;

    for(i=1; i<=n; ++i)
    {
        cin >> a[i].x >> a[i].y >> a[i].h;
        xs[a[i].x] = 1;
        ys[a[i].y] = 1;
    }

    for(i=1; i<=q; ++i)
        cin >> b[i].xl >> b[i].yl >> b[i].xh >> b[i].yh;

    normalize();

    for(i=1; i<=q; ++i)
    {
        events.push_back({ b[i].xl, {-1, i} });
        events.push_back({ b[i].xh, {+1, i} });
    }

    for(i=1; i<=n; ++i)
    {
        events.push_back({ a[i].x, {0, i} });
    }

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

    lim = n;

    for(auto it : events)
    {
        int tip = it.second.first;
        int id = it.second.second;

        currX = it.first;

        if(tip == -1)
        {
            if(b[id].yl <= b[id].yh)
                aint.add(1, 1, lim, b[id].yl, b[id].yh, id);
        }

        //if(tip == +1) aint.del(1, 1, lim, b[val].yl, b[val].yh, val);
        if(tip == 0) aint.update(1, 1, lim, a[id].y, a[id].h);
    }

    for(i=1; i<=q; ++i)
        cout << get_result(b[i].v) << '\n';

    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 25948kb

input:

9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3

output:

0
1
0
1
1

result:

wrong answer 4th lines differ - expected: '0', found: '1'