Submission #829630

#	Time	Username	Problem	Language	Result	Execution time	Memory
829630		erdemkiraz	New Home (APIO18_new_home)	C++17	10 / 100	1941 ms	153868 KiB

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 (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20