Submission #829630

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829630	2023-08-18T13:35:34 Z	erdemkiraz	New Home (APIO18_new_home)	C++17	10 / 100	1941 ms	153868 KB

new_home

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair < int, int > ii;
 
const int N = 3e5 + 5;
const int OUT = 0, QUE = 1;
const int addPositive = 0, addNegative = 1;
 
int n, q, k, total;
int ans[N];
map < int, int > s[N];
 
int z, g;
 
int tree[2][N << 1];
 
int curX;
vector < pair < int, pair < int*, int > > > changes;
 
void update(int t, int l, int r, int x) {
    for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
        if((l & 1) and x > tree[t][l]) {
            changes.push_back({curX, {&tree[t][l], tree[t][l]}});
            tree[t][l] = x;
        }
        if((~r & 1) and x > tree[t][r]) {
            changes.push_back({curX, {&tree[t][r], tree[t][r]}});
            tree[t][r] = x;
        }
    }
}
 
int get(int t, int x) {
    int res = -1e9;
    x += N;
    while(x >= 1) {
        res = max(res, tree[t][x]);
        x >>= 1;
    }
    return res;
}
 
inline int read() {
    char c = getchar();
    int x = 0;
    while(c < '0' or c > '9')
        c = getchar();
    while('0' <= c and c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
 
vector < pair < ii, int > > M[N * 4];
int isany[N * 4];
 
bool create(int x, int type, int l, int r, int x1, int x2, int v, int y) {
    if(x2 < l or r < x1)
        return false;
    if(type == QUE)
        isany[x] = 1;
    if(x1 <= l and r <= x2) {
        // printf("type = %d l = %d r = %d\n", type, l, r);
        M[x].push_back({{type, v}, y});
        return type == OUT;
    }
    int m = (l + r) >> 1;
    if(create(x + x, type, l, m, x1, x2, v, y)) {
        return true;
    }
    return create(x + x + 1, type, m + 1, r, x1, x2, v, y);
}
 
vector < int > ques;
int rid(int x) {
    return lower_bound(ques.begin(), ques.end(), x) - ques.begin() + 1;
}
int lid(int x) {
    return upper_bound(ques.begin(), ques.end(), x) - ques.begin();
}
 
vector < int > ins;
int ri(int x) {
    return lower_bound(ins.begin(), ins.end(), x) - ins.begin() + 1;
}
int li(int x) {
    return upper_bound(ins.begin(), ins.end(), x) - ins.begin();
}
 
void solve(int x, int l, int r) {
    if(!isany[x])
        return;
 
    int delTotal = 0;
 
    curX = x;
 
    bool HARD_FAIL = 0;
 
    for(auto tmp : M[x]) {
        int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
        if(type == OUT) {
            if(--s[t][x])
                continue;
            s[t].erase(x);
            // printf("deleting location = %d type = %d\n", x, t);
            auto it = s[t].begin();
            int nxt = (it=s[t].upper_bound(x)) == s[t].end() ? -1 : it->first;
                int bef = (it=s[t].lower_bound(x)) == s[t].begin() ? -1 : (--it)->first;
            if(bef == -1 and nxt == -1) {
                HARD_FAIL = 1;
            }
            else if(bef == -1) {
                update(addNegative, 1, lid((x + nxt) / 2), nxt);
            }
            else if(nxt == -1) {
                update(addPositive, rid((bef + x) / 2 + 1), z, -bef);
            }
            else {
                update(addPositive, rid((bef + x) / 2 + 1), lid((bef + nxt) / 2), -bef);
                update(addNegative, rid((bef + nxt) / 2 + 1), lid((x + nxt) / 2), nxt);
            }
        }
    }
 
    // if(HARD_FAIL) {
    //     for(auto tmp : M[x]) {
    //         int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
    //         if(type == OUT) {
    //             // printf("reverting x = %d t = %d\n", x, t);
    //             s[t][x]++;
    //         }
    //     }
 
    //     while(!changes.empty() and changes.back().first == x) {
    //         *changes.back().second.first = changes.back().second.second;
    //         changes.pop_back();
    //     }
    //     return;
    // }
 
    if(l == r) {
        for(auto tmp : M[x]) {
            int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
            if(type == QUE) {
                int a = get(0, rid(x));
                int b = get(1, rid(x));
                // printf("que x = %d i = %d a = %d b = %d\n", x, t, a, b);
                ans[t] = max(a + x, b - x);
            }
        }
    }
    else {
        int m = (l + r) >> 1;
        solve(x + x, l, m);
        solve(x + x + 1, m + 1, r);
    }
 
    // for(auto tmp : M[x]) {
    //     int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
    //     if(type == OUT) {
    //         // printf("reverting x = %d t = %d\n", x, t);
    //         s[t][x]++;
    //     }
    // }
 
    // while(!changes.empty() and changes.back().first == x) {
    //     *changes.back().second.first = changes.back().second.second;
    //     changes.pop_back();
    // }
 
}
 
int x1[N], t1[N], a1[N], b1[N], x2[N], y2[N];
 
int main() {
 
    n = read();
    k = read();
    q = read();
 
    for(int i = 1; i <= n; i++) {
        int x, t, a, b;
        x = read();
        t = read();
        a = read();
        b = read();
        assert(a == 1);
        x1[i]=x,t1[i]=t,a1[i]=a,b1[i]=b;
    }
 
    for(int i = 1; i <= q; i++) {
        int x, y;
        x = read();
        y = read();
        x2[i] = x;
        y2[i] = y;
        ins.push_back(y);
        ques.push_back(x);
    }
 
    sort(ques.begin(), ques.end());
    ques.resize(unique(ques.begin(), ques.end()) - ques.begin());
    z = ques.size();
 
    ins.push_back(0);
    ins.push_back(1e8 + 1);
 
    sort(ins.begin(), ins.end());
    ins.resize(unique(ins.begin(), ins.end()) - ins.begin());
    g = ins.size();
 
    for(int i = 1; i <= n; i++) {
        int x=x1[i], t=t1[i], a=a1[i], b=b1[i];
        s[t][x]++;
        a = li(a - 1);
        b = ri(b + 1);
        if(a != 1) {
            create(1, OUT, 1, g, 1, a, x, t);
        }
        if(b != g) {
            create(1, OUT, 1, g, b, g, x, t);
        }
    }
 
    for(int i = 1; i <= q; i++) {
        int x=x2[i], y=y2[i];
        ans[i] = -1;
        create(1, QUE, 1, g, ri(y), ri(y), x, i);
    }
 
    memset(tree, -63, sizeof(tree));
 
    for(int i = 1; i <= k; i++) {
        vector < int > v;
        for(auto x : s[i])
            v.push_back(x.first);
        if(v.empty())
            break;
        total++;
        update(addNegative, 1, rid(v[0]), v[0]);
        for(int it = 0; it + 1 < v.size(); it++) {
            update(addPositive, rid(v[it]), lid((v[it] + v[it + 1]) / 2), -v[it]);
            update(addNegative, rid((v[it] + v[it + 1]) / 2 + 1), lid(v[it + 1]), v[it + 1]);
        }
        update(addPositive, rid(v.back()), z, -v.back());
    }
 
    changes.clear();
 
    if(total == k)
        solve(1, 1, g);
 
    for(int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
 
    return 0;
 
}

Compilation message

new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:98:9: warning: unused variable 'delTotal' [-Wunused-variable]
   98 |     int delTotal = 0;
      |         ^~~~~~~~
new_home.cpp:102:10: warning: variable 'HARD_FAIL' set but not used [-Wunused-but-set-variable]
  102 |     bool HARD_FAIL = 0;
      |          ^~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:246:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |         for(int it = 0; it + 1 < v.size(); it++) {
      |                         ~~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47316 KB	Output is correct
2	Runtime error	50 ms	86096 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47316 KB	Output is correct
2	Runtime error	50 ms	86096 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	973 ms	149816 KB	Output is correct
2	Correct	841 ms	124248 KB	Output is correct
3	Correct	852 ms	125388 KB	Output is correct
4	Correct	941 ms	149832 KB	Output is correct
5	Correct	800 ms	106720 KB	Output is correct
6	Correct	837 ms	124324 KB	Output is correct
7	Correct	707 ms	125444 KB	Output is correct
8	Correct	879 ms	149828 KB	Output is correct
9	Correct	878 ms	149744 KB	Output is correct
10	Correct	806 ms	149128 KB	Output is correct
11	Correct	550 ms	148328 KB	Output is correct
12	Correct	605 ms	148944 KB	Output is correct