Submission #829633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829633	2023-08-18T13:37:53 Z	erdemkiraz	New Home (APIO18_new_home)	C++17	10 / 100	1471 ms	141088 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	22 ms	47316 KB	Output is correct
2	Runtime error	61 ms	86124 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	22 ms	47316 KB	Output is correct
2	Runtime error	61 ms	86124 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	981 ms	136148 KB	Output is correct
2	Correct	844 ms	111636 KB	Output is correct
3	Correct	761 ms	111548 KB	Output is correct
4	Correct	856 ms	136140 KB	Output is correct
5	Correct	675 ms	94268 KB	Output is correct
6	Correct	717 ms	111884 KB	Output is correct
7	Correct	665 ms	111584 KB	Output is correct
8	Correct	755 ms	136216 KB	Output is correct
9	Correct	750 ms	136148 KB	Output is correct
10	Correct	720 ms	136200 KB	Output is correct
11	Correct	497 ms	135836 KB	Output is correct
12	Correct	552 ms	136164 KB	Output is correct