oj.uz

답안 #171238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171238 2019-12-28T04:14:27 Z arnold518 새 집 (APIO18_new_home) C++14
5 / 100
 34 ms 18100 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;
const int INF = 2e8;

struct Data { int x, t, a, b; };
struct Query { int l, y, p; };

int N, K, Q, C;
Data A[MAXN*2+10];
Query query[MAXN+10];
vector<int> comp;
int ans[MAXN+10];

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }

struct Line
{
    int x, y;
    Line() {}
    Line(int x, int y) : x(x), y(y) {}
    bool operator < (const Line &p) const { return pii(x, y)<pii(p.x, p.y); }
};

Line Line1(int x, int y) { return Line(x, y-x); }
Line Line2(int x, int y) { return Line(y, y-x); }

multiset<int> S[MAXN+10];

//==================================================

map<Line, pii> M1;
vector<Line> tree1[MAXN*12+10];

void update1(int node, int tl, int tr, int l, int r, Line val)
{
    if(l<=tl && tr<=r) { tree1[node].push_back(val); return; }
    if(r<tl || tr<l) return;
    int mid=tl+tr>>1;
    update1(node*2, tl, mid, l, r, val);
    update1(node*2+1, mid+1, tr, l, r, val);
}

void pushLine1(int x, int y, int t)
{
    Line p=Line1(x, y);
    if(M1[p].second==0) M1[p].first=t;
    M1[p].second++;
}

void popLine1(int x, int y, int t)
{
    Line p=Line1(x, y);
    M1[p].second--;
    if(M1[p].second==0) update1(1, 1, C, M1[p].first, t, p);
}

//==================================================

map<Line, pii> M2;
vector<Line> tree2[MAXN*12+10];

void update2(int node, int tl, int tr, int l, int r, Line val)
{
    if(l<=tl && tr<=r) { tree2[node].push_back(val); return; }
    if(r<tl || tr<l) return;
    int mid=tl+tr>>1;
    update2(node*2, tl, mid, l, r, val);
    update2(node*2+1, mid+1, tr, l, r, val);
}

void pushLine2(int x, int y, int t)
{
    Line p=Line2(x, y);
    if(M2[p].second==0) M2[p].first=t;
    M2[p].second++;
}

void popLine2(int x, int y, int t)
{
    Line p=Line2(x, y);
    M2[p].second--;
    if(M2[p].second==0) update2(1, 1, C, M2[p].first, t, p);
}

//==================================================

vector<Query> tree3[MAXN*12+10];
vector<int> tree4[MAXN*12+10];
multiset<int> SS; int cnt=0;

void update3(int node, int tl, int tr, int pos, Query val)
{
    tree3[node].push_back(val);
    if(tl==tr) return;
    int mid=tl+tr>>1;
    if(pos<=mid) update3(node*2, tl, mid, pos, val);
    else update3(node*2+1, mid+1, tr, pos, val);
}

void update4(int node, int tl, int tr, int l, int r, int val)
{
    if(l<=tl && tr<=r) { tree4[node].push_back(val); return; }
    if(r<tl || tr<l) return;
    int mid=tl+tr>>1;
    update4(node*2, tl, mid, l, r, val);
    update4(node*2+1, mid+1, tr, l, r, val);
}

void dfs(int node, int tl, int tr)
{
    int i, j;

    //printf("%d %d %d\n", node, tl, tr);
    //printf("==============S\n");
    //for(auto it : tree1[node]) printf("%d %d / ", it.x, it.y); printf("\n");
    //for(auto it : tree2[node]) printf("%d %d / ", it.x, it.y); printf("\n");
    //for(auto it : tree3[node]) printf("%d %d / ", it.l, it.y); printf("\n");
    //printf("==============E\n");

    sort(tree1[node].begin(), tree1[node].end(), [&](const Line &p, const Line &q) { return p.x!=q.x ? p.x<q.x : p.y<q.y; });
    sort(tree3[node].begin(), tree3[node].end(), [&](const Query &p, const Query &q) { return p.l<q.l; });

    for(auto it : tree4[node])
    {
        if(SS.find(it)==SS.end()) cnt++;
        SS.insert(it);
    }

    int val=-1;
    for(i=0, j=0; i<tree3[node].size(); i++)
    {
        Query now=tree3[node][i];
        for(; j<tree1[node].size() && tree1[node][j].x<=now.l; j++)
        {
            Line t=tree1[node][j];
            val=max(val, t.x+t.y);
            ans[now.p]=max(ans[now.p], val-now.l);
            //printf("!%d %d\n", i, j);
        }
        if(j) j--;
    }

    sort(tree2[node].begin(), tree2[node].end(), [&](const Line &p, const Line &q) { return p.x!=q.x ? p.x>q.x : p.y<q.y; });
    sort(tree3[node].begin(), tree3[node].end(), [&](const Query &p, const Query &q) { return p.l>q.l; });

    val=INF+1;
    for(i=0, j=0; i<tree3[node].size(); i++)
    {
        Query now=tree3[node][i];
        for(; j<tree2[node].size() && tree2[node][j].x>=now.l; j++)
        {
            Line t=tree2[node][j];
            val=min(val, t.x-t.y);
            ans[now.p]=max(ans[now.p], now.l-val);
        }
        if(j) j--;
    }

    if(tl==tr)
    {
        if(cnt!=K) for(auto it : tree3[node]) ans[it.p]=-2;

        for(auto it : tree4[node])
        {
            SS.erase(SS.find(it));
            if(SS.find(it)==SS.end()) cnt--;
        }
        return;
    }

    int mid=tl+tr>>1;
    dfs(node*2, tl, mid);
    dfs(node*2+1, mid+1, tr);

    for(auto it : tree4[node])
    {
        SS.erase(SS.find(it));
        if(SS.find(it)==SS.end()) cnt--;
    }
}

int main()
{
    int i, j;

    scanf("%d%d%d", &N, &K, &Q);
    for(i=1; i<=N; i++)
    {
        int x, t, a, b;
        scanf("%d%d%d%d", &x, &t, &a, &b); x*=2; a=a*3-1; b=b*3+1;
        A[i*2-1]={x, t, a, -1};
        A[i*2]={x, t, b, 1};
        comp.push_back(a);
        comp.push_back(b);
    }

    for(i=1; i<=Q; i++)
    {
        scanf("%d%d", &query[i].l, &query[i].y); query[i].y*=3;
        query[i].p=i;
        comp.push_back(query[i].y); query[i].l*=2;
    }

    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    C=comp.size();

    for(i=1; i<=2*N; i++) A[i].a=getcomp(A[i].a);
    for(i=1; i<=N; i++) update4(1, 1, C, A[i*2-1].a, A[i*2].a, A[i*2].t);
    for(i=1; i<=Q; i++) query[i].y=getcomp(query[i].y);
    for(i=1; i<=Q; i++) update3(1, 1, C, query[i].y, query[i]);

    sort(A+1, A+N+N+1, [&](const Data &p, const Data &q) { return p.a<q.a; });

    for(i=1; i<=N+N; i++)
    {
        Data now=A[i];
        int x, t, a, b;
        x=now.x; t=now.t; a=now.a; b=now.b;
        //printf("%d %d %d %d\n", x, t, a, b);
        if(b==-1)
        {
            if(S[t].find(x)==S[t].end())
            {
                if(S[t].size()==0)
                {
                    pushLine1(0, x, a);
                    pushLine2(x, INF, a);
                }
                else
                {
                    auto it=S[t].lower_bound(x);
                    int l, r;
                    if(it==S[t].end())
                    {
                        l=*prev(it);
                        popLine2(l, INF, a);
                        pushLine2(l, l+x>>1, a);
                        pushLine1(l+x>>1, x, a);
                        pushLine2(x, INF, a);
                    }
                    else if(it==S[t].begin())
                    {
                        r=*it;
                        popLine1(0, r, a);
                        pushLine1(0, x, a);
                        pushLine2(x, r+x>>1, a);
                        pushLine1(r+x>>1, r, a);
                    }
                    else
                    {
                        r=*it, l=*prev(it);
                        popLine2(l, l+r>>1, a);
                        popLine1(l+r>>1, r, a);
                        pushLine2(l, l+x>>1, a);
                        pushLine1(l+x>>1, x, a);
                        pushLine2(x, x+r>>1, a);
                        pushLine1(x+r>>1, r, a);
                    }
                }
            }
            S[t].insert(x);
        }
        else
        {
            S[t].erase(S[t].find(x));
            if(S[t].find(x)==S[t].end())
            {
                if(S[t].size()==0)
                {
                    popLine1(0, x, a);
                    popLine2(x, INF, a);
                }
                else
                {
                    auto it=S[t].lower_bound(x);
                    int l, r;
                    if(it==S[t].end())
                    {
                        l=*prev(it);
                        pushLine2(l, INF, a);
                        popLine2(l, l+x>>1, a);
                        popLine1(l+x>>1, x, a);
                        popLine2(x, INF, a);
                    }
                    else if(it==S[t].begin())
                    {
                        r=*it;
                        pushLine1(0, r, a);
                        popLine1(0, x, a);
                        popLine2(x, r+x>>1, a);
                        popLine1(r+x>>1, r, a);
                    }
                    else
                    {
                        r=*it, l=*prev(it);
                        pushLine2(l, l+r>>1, a);
                        pushLine1(l+r>>1, r, a);
                        popLine2(l, l+x>>1, a);
                        popLine1(l+x>>1, x, a);
                        popLine2(x, x+r>>1, a);
                        popLine1(x+r>>1, r, a);
                    }
                }
            }
        }
    }
    dfs(1, 1, C);

    for(i=1; i<=Q; i++) printf("%d\n", ans[i]/2);
}

Compilation message

new_home.cpp: In function 'void update1(int, int, int, int, int, Line)':
new_home.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update2(int, int, int, int, int, Line)':
new_home.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update3(int, int, int, int, Query)':
new_home.cpp:101:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void update4(int, int, int, int, int, int)':
new_home.cpp:110:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'void dfs(int, int, int)':
new_home.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; j<tree1[node].size() && tree1[node][j].x<=now.l; j++)
               ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<tree3[node].size(); i++)
                   ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; j<tree2[node].size() && tree2[node][j].x>=now.l; j++)
               ~^~~~~~~~~~~~~~~~~~~
new_home.cpp:177:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:244:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:245:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:253:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, r+x>>1, a);
                                      ~^~
new_home.cpp:254:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(r+x>>1, r, a);
                                   ~^~
new_home.cpp:259:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+r>>1, a);
                                     ~^~
new_home.cpp:260:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+r>>1, r, a);
                                  ~^~
new_home.cpp:261:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+x>>1, a);
                                      ~^~
new_home.cpp:262:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+x>>1, x, a);
                                   ~^~
new_home.cpp:263:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(x, x+r>>1, a);
                                      ~^~
new_home.cpp:264:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(x+r>>1, r, a);
                                   ~^~
new_home.cpp:288:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:289:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:297:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, r+x>>1, a);
                                     ~^~
new_home.cpp:298:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(r+x>>1, r, a);
                                  ~^~
new_home.cpp:303:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine2(l, l+r>>1, a);
                                      ~^~
new_home.cpp:304:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         pushLine1(l+r>>1, r, a);
                                   ~^~
new_home.cpp:305:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(l, l+x>>1, a);
                                     ~^~
new_home.cpp:306:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(l+x>>1, x, a);
                                  ~^~
new_home.cpp:307:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine2(x, x+r>>1, a);
                                     ~^~
new_home.cpp:308:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         popLine1(x+r>>1, r, a);
                                  ~^~
new_home.cpp:190:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
new_home.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &a, &b); x*=2; a=a*3-1; b=b*3+1;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:205:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &query[i].l, &query[i].y); query[i].y*=3;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6396 KB Output is correct
3 Correct 8 ms 6268 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Correct 34 ms 6520 KB Output is correct
6 Correct 16 ms 6776 KB Output is correct
7 Correct 13 ms 6520 KB Output is correct
8 Correct 15 ms 6652 KB Output is correct
9 Correct 13 ms 6632 KB Output is correct
10 Correct 25 ms 6904 KB Output is correct
11 Correct 12 ms 6392 KB Output is correct
12 Correct 13 ms 6648 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 12 ms 6520 KB Output is correct
15 Correct 13 ms 6648 KB Output is correct
16 Correct 14 ms 6636 KB Output is correct
17 Correct 14 ms 6776 KB Output is correct
18 Correct 14 ms 6648 KB Output is correct
19 Correct 14 ms 6648 KB Output is correct
20 Correct 14 ms 6648 KB Output is correct
21 Correct 9 ms 6264 KB Output is correct
22 Correct 14 ms 6548 KB Output is correct
23 Correct 15 ms 6648 KB Output is correct
24 Correct 13 ms 6648 KB Output is correct
25 Correct 13 ms 6652 KB Output is correct
26 Correct 12 ms 6648 KB Output is correct
27 Correct 11 ms 6392 KB Output is correct
28 Correct 12 ms 6648 KB Output is correct
29 Correct 11 ms 6520 KB Output is correct
30 Correct 9 ms 6524 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6396 KB Output is correct
3 Correct 8 ms 6268 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Correct 34 ms 6520 KB Output is correct
6 Correct 16 ms 6776 KB Output is correct
7 Correct 13 ms 6520 KB Output is correct
8 Correct 15 ms 6652 KB Output is correct
9 Correct 13 ms 6632 KB Output is correct
10 Correct 25 ms 6904 KB Output is correct
11 Correct 12 ms 6392 KB Output is correct
12 Correct 13 ms 6648 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 12 ms 6520 KB Output is correct
15 Correct 13 ms 6648 KB Output is correct
16 Correct 14 ms 6636 KB Output is correct
17 Correct 14 ms 6776 KB Output is correct
18 Correct 14 ms 6648 KB Output is correct
19 Correct 14 ms 6648 KB Output is correct
20 Correct 14 ms 6648 KB Output is correct
21 Correct 9 ms 6264 KB Output is correct
22 Correct 14 ms 6548 KB Output is correct
23 Correct 15 ms 6648 KB Output is correct
24 Correct 13 ms 6648 KB Output is correct
25 Correct 13 ms 6652 KB Output is correct
26 Correct 12 ms 6648 KB Output is correct
27 Correct 11 ms 6392 KB Output is correct
28 Correct 12 ms 6648 KB Output is correct
29 Correct 11 ms 6520 KB Output is correct
30 Correct 9 ms 6524 KB Output is correct
31 Incorrect 13 ms 6876 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 18100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 15608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6396 KB Output is correct
3 Correct 8 ms 6268 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Correct 34 ms 6520 KB Output is correct
6 Correct 16 ms 6776 KB Output is correct
7 Correct 13 ms 6520 KB Output is correct
8 Correct 15 ms 6652 KB Output is correct
9 Correct 13 ms 6632 KB Output is correct
10 Correct 25 ms 6904 KB Output is correct
11 Correct 12 ms 6392 KB Output is correct
12 Correct 13 ms 6648 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 12 ms 6520 KB Output is correct
15 Correct 13 ms 6648 KB Output is correct
16 Correct 14 ms 6636 KB Output is correct
17 Correct 14 ms 6776 KB Output is correct
18 Correct 14 ms 6648 KB Output is correct
19 Correct 14 ms 6648 KB Output is correct
20 Correct 14 ms 6648 KB Output is correct
21 Correct 9 ms 6264 KB Output is correct
22 Correct 14 ms 6548 KB Output is correct
23 Correct 15 ms 6648 KB Output is correct
24 Correct 13 ms 6648 KB Output is correct
25 Correct 13 ms 6652 KB Output is correct
26 Correct 12 ms 6648 KB Output is correct
27 Correct 11 ms 6392 KB Output is correct
28 Correct 12 ms 6648 KB Output is correct
29 Correct 11 ms 6520 KB Output is correct
30 Correct 9 ms 6524 KB Output is correct
31 Incorrect 13 ms 6876 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6396 KB Output is correct
3 Correct 8 ms 6268 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Correct 34 ms 6520 KB Output is correct
6 Correct 16 ms 6776 KB Output is correct
7 Correct 13 ms 6520 KB Output is correct
8 Correct 15 ms 6652 KB Output is correct
9 Correct 13 ms 6632 KB Output is correct
10 Correct 25 ms 6904 KB Output is correct
11 Correct 12 ms 6392 KB Output is correct
12 Correct 13 ms 6648 KB Output is correct
13 Correct 12 ms 6520 KB Output is correct
14 Correct 12 ms 6520 KB Output is correct
15 Correct 13 ms 6648 KB Output is correct
16 Correct 14 ms 6636 KB Output is correct
17 Correct 14 ms 6776 KB Output is correct
18 Correct 14 ms 6648 KB Output is correct
19 Correct 14 ms 6648 KB Output is correct
20 Correct 14 ms 6648 KB Output is correct
21 Correct 9 ms 6264 KB Output is correct
22 Correct 14 ms 6548 KB Output is correct
23 Correct 15 ms 6648 KB Output is correct
24 Correct 13 ms 6648 KB Output is correct
25 Correct 13 ms 6652 KB Output is correct
26 Correct 12 ms 6648 KB Output is correct
27 Correct 11 ms 6392 KB Output is correct
28 Correct 12 ms 6648 KB Output is correct
29 Correct 11 ms 6520 KB Output is correct
30 Correct 9 ms 6524 KB Output is correct
31 Incorrect 13 ms 6876 KB Output isn't correct
32 Halted 0 ms 0 KB -