oj.uz

Submission #159495

# Submission time Handle Problem Language Result Execution time Memory
159495 2019-10-23T00:56:27 Z arnold518 New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 526204 KB 
#include <bits/stdc++.h>
#pragma gcc optimize "03"
using namespace std;

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

const int MAXN = 3e5;
const int MAXVAL = 1e8;

struct Query
{
    int t, x, k, p;
    bool operator < (const Query &p)
    {
        if(t!=p.t) return t<p.t;
        return k>p.k;
    }
};

int N, K, Q, ans[MAXN+10], SZ, chk;
vector<Query> query;
multiset<int> S[MAXN+10];
set<int> scomp;
vector<int> comp;

int getcomp(int x)
{
    //for(auto it : comp) printf("%d ", it); printf("-> %d\n", x);
    assert(binary_search(comp.begin(), comp.end(), x));
    return lower_bound(comp.begin(), comp.end(), x)-comp.begin();
}

priority_queue<int, vector<int>, less<int>> tree1[4*MAXN+10];
priority_queue<int, vector<int>, less<int>> dead1[4*MAXN+10];

priority_queue<int, vector<int>, greater<int>> tree2[4*MAXN+10];
priority_queue<int, vector<int>, greater<int>> dead2[4*MAXN+10];

ll query1(int x)
{
    int y=x;
    x=getcomp(x);
    int ret=0;
    for(; x>0; x-=(x&-x))
    {
        while(!tree1[x].empty() && !dead1[x].empty() && tree1[x].top()==dead1[x].top()) tree1[x].pop(), dead1[x].pop();
        if(!tree1[x].empty())
        {
            ////printf("QUERY1 %d %d\n", x, tree1[x].top()-y);
            ret=max(ret, tree1[x].top()-y);
        }
    }
    return ret;
}

void erase1(int x, int y)
{
    ////printf("ERASE1 %d %d\n", x, y);
    x=getcomp(x);
    for(; x<=SZ; x+=(x&-x))
    {
        dead1[x].push(y);
    }
}

void insert1(int x, int y)
{
    //printf("INSERT1 %d %d\n", x, y);
    x=getcomp(x);
    for(; x<=SZ; x+=(x&-x))
    {
        tree1[x].push(y);
    }
}

ll query2(int x)
{
    int y=x;
    x=getcomp(x);
    x=SZ-x+1;
    int ret=0;
    for(; x>0; x-=(x&-x))
    {
        while(!tree2[x].empty() && !dead2[x].empty() && tree2[x].top()==dead2[x].top()) tree2[x].pop(), dead2[x].pop();
        if(!tree2[x].empty())
        {
            ////printf("QUERY1 %d %d\n", x, y-tree2[x].top());
            ret=max(ret, y-tree2[x].top());
        }
    }
    return ret;
}

void erase2(int x, int y)
{
    swap(x, y);
    ////printf("ERASE2 %d %d\n", x, y);
    x=getcomp(x);
    x=SZ-x+1;
    for(; x<=SZ; x+=(x&-x))
    {
        dead2[x].push(y);
    }
}

void insert2(int x, int y)
{
    //printf("INSERT2 %d %d\n", x, y);
    swap(x, y);
    x=getcomp(x);
    x=SZ-x+1;
    for(; x<=SZ; x+=(x&-x))
    {
        tree2[x].push(y);
    }
}

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); b++; x*=2;
        query.push_back({a, x, t, 1});
        query.push_back({b, x, t, -1});
        scomp.insert(x);
    }
    for(i=1; i<=Q; i++)
    {
        int l, x;
        scanf("%d%d", &x, &l); x*=2;
        query.push_back({l, x, -i, 0});
        scomp.insert(x);
    }
    sort(query.begin(), query.end());

    scomp.insert(0); scomp.insert(2e8);
    for(auto now : query)
    {
        int x=now.x;
        if(now.p==1)
        {
            if(S[now.k].find(x)==S[now.k].end())
            {
                if(S[now.k].size()!=0)
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*prev(it);
                    if(it==S[now.k].end()) scomp.insert(l+x>>1);
                    else if(it==S[now.k].begin()) scomp.insert(r+x>>1);
                    else
                    {
                        scomp.insert(l+x>>1);
                        scomp.insert(r+x>>1);
                    }
                }
            }
            S[now.k].insert(x);
        }
        else if(now.p==-1)
        {
            S[now.k].erase(S[now.k].find(x));
            if(S[now.k].find(x)==S[now.k].end())
            {
                if(S[now.k].size()!=0)
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*prev(it);
                    if(it==S[now.k].end());
                    else if(it==S[now.k].begin());
                    else scomp.insert(l+r>>1);
                }
            }
        }
    }

    comp.push_back(-1);
    for(auto it : scomp) comp.push_back(it);
    SZ=scomp.size();

    for(i=1; i<=K; i++) S[i].clear();

    for(auto now : query)
    {
        //printf("===============\n");
        int x=now.x;
        if(now.p==0)
        {
            if(chk!=K) ans[-now.k]=-1;
            else ans[-now.k]=max(query1(x), query2(x))>>1;
            //printf("!%d %d %d\n", -now.k, query1(x), query2(x));
        }
        else if(now.p==1)
        {
            if(S[now.k].find(now.x)==S[now.k].end())
            {
                if(S[now.k].size()==0)
                {
                    insert1(0, x);
                    insert2(x, 2e8);
                    chk++;
                }
                else
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*prev(it);
                    if(it==S[now.k].end())
                    {
                        erase2(l, 2e8);
                        insert2(l, l+x>>1);
                        insert1(l+x>>1, x);
                        insert2(x, 2e8);
                    }
                    else if(it==S[now.k].begin())
                    {
                        erase1(0, r);
                        insert1(0, x);
                        insert2(x, r+x>>1);
                        insert1(r+x>>1, r);
                    }
                    else
                    {
                        erase2(l, l+r>>1);
                        erase1(l+r>>1, r);
                        insert2(l, l+x>>1);
                        insert1(l+x>>1, x);
                        insert2(x, x+r>>1);
                        insert1(x+r>>1, r);
                    }
                }
            }
            S[now.k].insert(now.x);
        }
        else if(now.p==-1)
        {
            S[now.k].erase(S[now.k].find(now.x));
            if(S[now.k].find(now.x)==S[now.k].end())
            {
                if(S[now.k].size()==0)
                {
                    erase1(0, x);
                    erase2(x, 2e8);
                    chk--;
                }
                else
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*prev(it);
                    if(it==S[now.k].end())
                    {
                        insert2(l, 2e8);
                        erase2(l, l+x>>1);
                        erase1(l+x>>1, x);
                        erase2(x, 2e8);
                    }
                    else if(it==S[now.k].begin())
                    {
                        insert1(0, r);
                        erase1(0, x);
                        erase2(x, r+x>>1);
                        erase1(r+x>>1, r);
                    }
                    else
                    {
                        insert2(l, l+r>>1);
                        insert1(l+r>>1, r);
                        erase2(l, l+x>>1);
                        erase1(l+x>>1, x);
                        erase2(x, x+r>>1);
                        erase1(x+r>>1, r);
                    }
                }
            }
        }
    }
    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message

new_home.cpp:2:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize "03"
 
new_home.cpp: In function 'int main()':
new_home.cpp:154:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     if(it==S[now.k].end()) scomp.insert(l+x>>1);
                                                         ~^~
new_home.cpp:155:65: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     else if(it==S[now.k].begin()) scomp.insert(r+x>>1);
                                                                ~^~
new_home.cpp:158:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         scomp.insert(l+x>>1);
                                      ~^~
new_home.cpp:159:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         scomp.insert(r+x>>1);
                                      ~^~
new_home.cpp:176:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     else scomp.insert(l+r>>1);
                                       ~^~
new_home.cpp:215:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(l, l+x>>1);
                                    ~^~
new_home.cpp:216:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(l+x>>1, x);
                                 ~^~
new_home.cpp:223:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(x, r+x>>1);
                                    ~^~
new_home.cpp:224:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(r+x>>1, r);
                                 ~^~
new_home.cpp:228:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(l, l+r>>1);
                                   ~^~
new_home.cpp:229:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(l+r>>1, r);
                                ~^~
new_home.cpp:230:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(l, l+x>>1);
                                    ~^~
new_home.cpp:231:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(l+x>>1, x);
                                 ~^~
new_home.cpp:232:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(x, x+r>>1);
                                    ~^~
new_home.cpp:233:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(x+r>>1, r);
                                 ~^~
new_home.cpp:257:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(l, l+x>>1);
                                   ~^~
new_home.cpp:258:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(l+x>>1, x);
                                ~^~
new_home.cpp:265:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(x, r+x>>1);
                                   ~^~
new_home.cpp:266:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(r+x>>1, r);
                                ~^~
new_home.cpp:270:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(l, l+r>>1);
                                    ~^~
new_home.cpp:271:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(l+r>>1, r);
                                 ~^~
new_home.cpp:272:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(l, l+x>>1);
                                   ~^~
new_home.cpp:273:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(l+x>>1, x);
                                ~^~
new_home.cpp:274:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(x, x+r>>1);
                                   ~^~
new_home.cpp:275:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(x+r>>1, r);
                                ~^~
new_home.cpp:122:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
new_home.cpp:124: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:128: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); b++; x*=2;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &l); x*=2;
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 164672 KB Output is correct
2 Correct 149 ms 164756 KB Output is correct
3 Correct 148 ms 164728 KB Output is correct
4 Correct 148 ms 164780 KB Output is correct
5 Correct 149 ms 164728 KB Output is correct
6 Correct 152 ms 164984 KB Output is correct
7 Correct 173 ms 164856 KB Output is correct
8 Correct 154 ms 165112 KB Output is correct
9 Correct 151 ms 164944 KB Output is correct
10 Correct 153 ms 165112 KB Output is correct
11 Correct 184 ms 165008 KB Output is correct
12 Correct 155 ms 165168 KB Output is correct
13 Correct 151 ms 164900 KB Output is correct
14 Correct 149 ms 164984 KB Output is correct
15 Correct 151 ms 164984 KB Output is correct
16 Correct 150 ms 164960 KB Output is correct
17 Correct 151 ms 165032 KB Output is correct
18 Correct 151 ms 164984 KB Output is correct
19 Correct 184 ms 164984 KB Output is correct
20 Correct 176 ms 164984 KB Output is correct
21 Correct 168 ms 164844 KB Output is correct
22 Correct 158 ms 164856 KB Output is correct
23 Correct 174 ms 164984 KB Output is correct
24 Correct 175 ms 164984 KB Output is correct
25 Correct 166 ms 165112 KB Output is correct
26 Correct 159 ms 164960 KB Output is correct
27 Correct 175 ms 164812 KB Output is correct
28 Correct 153 ms 165028 KB Output is correct
29 Correct 160 ms 165128 KB Output is correct
30 Correct 160 ms 164920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 164672 KB Output is correct
2 Correct 149 ms 164756 KB Output is correct
3 Correct 148 ms 164728 KB Output is correct
4 Correct 148 ms 164780 KB Output is correct
5 Correct 149 ms 164728 KB Output is correct
6 Correct 152 ms 164984 KB Output is correct
7 Correct 173 ms 164856 KB Output is correct
8 Correct 154 ms 165112 KB Output is correct
9 Correct 151 ms 164944 KB Output is correct
10 Correct 153 ms 165112 KB Output is correct
11 Correct 184 ms 165008 KB Output is correct
12 Correct 155 ms 165168 KB Output is correct
13 Correct 151 ms 164900 KB Output is correct
14 Correct 149 ms 164984 KB Output is correct
15 Correct 151 ms 164984 KB Output is correct
16 Correct 150 ms 164960 KB Output is correct
17 Correct 151 ms 165032 KB Output is correct
18 Correct 151 ms 164984 KB Output is correct
19 Correct 184 ms 164984 KB Output is correct
20 Correct 176 ms 164984 KB Output is correct
21 Correct 168 ms 164844 KB Output is correct
22 Correct 158 ms 164856 KB Output is correct
23 Correct 174 ms 164984 KB Output is correct
24 Correct 175 ms 164984 KB Output is correct
25 Correct 166 ms 165112 KB Output is correct
26 Correct 159 ms 164960 KB Output is correct
27 Correct 175 ms 164812 KB Output is correct
28 Correct 153 ms 165028 KB Output is correct
29 Correct 160 ms 165128 KB Output is correct
30 Correct 160 ms 164920 KB Output is correct
31 Correct 1860 ms 235248 KB Output is correct
32 Correct 259 ms 169152 KB Output is correct
33 Correct 1843 ms 236352 KB Output is correct
34 Correct 1782 ms 233408 KB Output is correct
35 Correct 1897 ms 236728 KB Output is correct
36 Correct 1910 ms 238568 KB Output is correct
37 Correct 1438 ms 234508 KB Output is correct
38 Correct 1452 ms 235744 KB Output is correct
39 Correct 1171 ms 233908 KB Output is correct
40 Correct 1213 ms 234972 KB Output is correct
41 Correct 1176 ms 213084 KB Output is correct
42 Correct 1077 ms 214748 KB Output is correct
43 Correct 227 ms 171108 KB Output is correct
44 Correct 1137 ms 212700 KB Output is correct
45 Correct 1182 ms 209780 KB Output is correct
46 Correct 1280 ms 202440 KB Output is correct
47 Correct 771 ms 211572 KB Output is correct
48 Correct 843 ms 212948 KB Output is correct
49 Correct 918 ms 213764 KB Output is correct
50 Correct 902 ms 214140 KB Output is correct
51 Correct 950 ms 212104 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2588 ms 526204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 164672 KB Output is correct
2 Correct 149 ms 164756 KB Output is correct
3 Correct 148 ms 164728 KB Output is correct
4 Correct 148 ms 164780 KB Output is correct
5 Correct 149 ms 164728 KB Output is correct
6 Correct 152 ms 164984 KB Output is correct
7 Correct 173 ms 164856 KB Output is correct
8 Correct 154 ms 165112 KB Output is correct
9 Correct 151 ms 164944 KB Output is correct
10 Correct 153 ms 165112 KB Output is correct
11 Correct 184 ms 165008 KB Output is correct
12 Correct 155 ms 165168 KB Output is correct
13 Correct 151 ms 164900 KB Output is correct
14 Correct 149 ms 164984 KB Output is correct
15 Correct 151 ms 164984 KB Output is correct
16 Correct 150 ms 164960 KB Output is correct
17 Correct 151 ms 165032 KB Output is correct
18 Correct 151 ms 164984 KB Output is correct
19 Correct 184 ms 164984 KB Output is correct
20 Correct 176 ms 164984 KB Output is correct
21 Correct 168 ms 164844 KB Output is correct
22 Correct 158 ms 164856 KB Output is correct
23 Correct 174 ms 164984 KB Output is correct
24 Correct 175 ms 164984 KB Output is correct
25 Correct 166 ms 165112 KB Output is correct
26 Correct 159 ms 164960 KB Output is correct
27 Correct 175 ms 164812 KB Output is correct
28 Correct 153 ms 165028 KB Output is correct
29 Correct 160 ms 165128 KB Output is correct
30 Correct 160 ms 164920 KB Output is correct
31 Correct 1860 ms 235248 KB Output is correct
32 Correct 259 ms 169152 KB Output is correct
33 Correct 1843 ms 236352 KB Output is correct
34 Correct 1782 ms 233408 KB Output is correct
35 Correct 1897 ms 236728 KB Output is correct
36 Correct 1910 ms 238568 KB Output is correct
37 Correct 1438 ms 234508 KB Output is correct
38 Correct 1452 ms 235744 KB Output is correct
39 Correct 1171 ms 233908 KB Output is correct
40 Correct 1213 ms 234972 KB Output is correct
41 Correct 1176 ms 213084 KB Output is correct
42 Correct 1077 ms 214748 KB Output is correct
43 Correct 227 ms 171108 KB Output is correct
44 Correct 1137 ms 212700 KB Output is correct
45 Correct 1182 ms 209780 KB Output is correct
46 Correct 1280 ms 202440 KB Output is correct
47 Correct 771 ms 211572 KB Output is correct
48 Correct 843 ms 212948 KB Output is correct
49 Correct 918 ms 213764 KB Output is correct
50 Correct 902 ms 214140 KB Output is correct
51 Correct 950 ms 212104 KB Output is correct
52 Correct 439 ms 194180 KB Output is correct
53 Correct 420 ms 192988 KB Output is correct
54 Correct 895 ms 214108 KB Output is correct
55 Correct 936 ms 209168 KB Output is correct
56 Correct 805 ms 206356 KB Output is correct
57 Correct 1059 ms 210964 KB Output is correct
58 Correct 914 ms 208656 KB Output is correct
59 Correct 802 ms 206112 KB Output is correct
60 Correct 1164 ms 211824 KB Output is correct
61 Correct 248 ms 172124 KB Output is correct
62 Correct 437 ms 194272 KB Output is correct
63 Correct 723 ms 208348 KB Output is correct
64 Correct 925 ms 211928 KB Output is correct
65 Correct 985 ms 215272 KB Output is correct
66 Correct 1147 ms 214172 KB Output is correct
67 Correct 364 ms 180444 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 164672 KB Output is correct
2 Correct 149 ms 164756 KB Output is correct
3 Correct 148 ms 164728 KB Output is correct
4 Correct 148 ms 164780 KB Output is correct
5 Correct 149 ms 164728 KB Output is correct
6 Correct 152 ms 164984 KB Output is correct
7 Correct 173 ms 164856 KB Output is correct
8 Correct 154 ms 165112 KB Output is correct
9 Correct 151 ms 164944 KB Output is correct
10 Correct 153 ms 165112 KB Output is correct
11 Correct 184 ms 165008 KB Output is correct
12 Correct 155 ms 165168 KB Output is correct
13 Correct 151 ms 164900 KB Output is correct
14 Correct 149 ms 164984 KB Output is correct
15 Correct 151 ms 164984 KB Output is correct
16 Correct 150 ms 164960 KB Output is correct
17 Correct 151 ms 165032 KB Output is correct
18 Correct 151 ms 164984 KB Output is correct
19 Correct 184 ms 164984 KB Output is correct
20 Correct 176 ms 164984 KB Output is correct
21 Correct 168 ms 164844 KB Output is correct
22 Correct 158 ms 164856 KB Output is correct
23 Correct 174 ms 164984 KB Output is correct
24 Correct 175 ms 164984 KB Output is correct
25 Correct 166 ms 165112 KB Output is correct
26 Correct 159 ms 164960 KB Output is correct
27 Correct 175 ms 164812 KB Output is correct
28 Correct 153 ms 165028 KB Output is correct
29 Correct 160 ms 165128 KB Output is correct
30 Correct 160 ms 164920 KB Output is correct
31 Correct 1860 ms 235248 KB Output is correct
32 Correct 259 ms 169152 KB Output is correct
33 Correct 1843 ms 236352 KB Output is correct
34 Correct 1782 ms 233408 KB Output is correct
35 Correct 1897 ms 236728 KB Output is correct
36 Correct 1910 ms 238568 KB Output is correct
37 Correct 1438 ms 234508 KB Output is correct
38 Correct 1452 ms 235744 KB Output is correct
39 Correct 1171 ms 233908 KB Output is correct
40 Correct 1213 ms 234972 KB Output is correct
41 Correct 1176 ms 213084 KB Output is correct
42 Correct 1077 ms 214748 KB Output is correct
43 Correct 227 ms 171108 KB Output is correct
44 Correct 1137 ms 212700 KB Output is correct
45 Correct 1182 ms 209780 KB Output is correct
46 Correct 1280 ms 202440 KB Output is correct
47 Correct 771 ms 211572 KB Output is correct
48 Correct 843 ms 212948 KB Output is correct
49 Correct 918 ms 213764 KB Output is correct
50 Correct 902 ms 214140 KB Output is correct
51 Correct 950 ms 212104 KB Output is correct
52 Execution timed out 5070 ms 413072 KB Time limit exceeded
53 Halted 0 ms 0 KB -