Submission #700722

#	Time	Username	Problem	Language	Result	Execution time	Memory
700722		primenumber_zz	Wall (IOI14_wall)	C++14	0 / 100	3073 ms	24884 KiB

wall

#include <bits/stdc++.h>
using namespace std;

struct DuelSegmentTree {
    int n;
    vector<int>dat;
    DuelSegmentTree(int N) {
        n = 1;
        while(n < N) {
            n *= 2;
        }
        dat.resize(2*n,-1);
    }
    void update(int l,int r,int x) {
        int now = l+n,le = l,ri = l+1;
        while(true) {
            if(now == 1) {
                dat[1] = max(dat[1],x);
                return;
            }
            int nle = 0,nri = 0;
            if(1&now) {
                nle = (le<<1)-ri;
                nri = ri;
            }
            else {
                nle = le;
                nri = (ri<<1)-le;
            }
            if(l <= nle && nri <= r) {
                now >>= 1;
                continue;
            }
            le = nle;
            ri = nri;
            dat[now] = max(dat[now],x);
            if(!(1&now)) {
                return;
            }
            while(1&now) {
                now >>= 1;
                le = (le<<1)-ri;
                ri = ri;
            }
            if(now == 0) return;
            now++;
            nle = ri;
            nri = (ri<<1)-le;
            if(l <= nle && nri <= r) {
                le = nle;
                ri = nri;
                continue;
            }
            break;
        }
        now = r+n-1,le = r-1,ri = r;
        while(true) {
            if(now == 1) {
                dat[1] = max(dat[1],x);
                return;
            }
            int nle = 0,nri = 0;
            if(1&now) {
                nle = (le<<1)-ri;
                nri = ri;
            }
            else {
                nle = le;
                nri = (ri<<1)-le;
            }
            if(l <= nle && nri <= r) {
                now >>= 1;
                continue;
            }
            dat[now] = max(dat[now],x);
            if((1&now)) {
                return;
            }
            le = nle;
            ri = nri;
            while(!(1&now)) {
                now >>= 1;
                le = le;
                ri = (ri<<1)-le;
            }
            if(now == 0) return;
            now--;
            nri = le;
            nle = (le<<1)-ri;
            if(l <= nle && nri <= r) {
                le = nle;
                ri = nri;
                continue;
            }
            break;
        }
    }
    int query(int x) {
        int ans = -1,now = x+n;
        while(now > 0) {
            ans = max(ans,dat[now]);
            now >>= 1;
        }
        return ans;
    }
};

void buildWall(int n, int k, int op[], int left[],int right[],int height[], int finalHeight[]) {
    int MAX = 0;
    for(int i = 0; i < k; i++) {
        MAX = max(MAX,height[i]);
    }
    vector<int>l(n,0),r(n,MAX+1);
    vector<array<int,3>>tmp1,tmp2;
    for(int i = 0; i < k; i++) {
        if(op[i] == 1) {
            tmp1.push_back({height[i],1,i});
        }
        else {
            tmp2.push_back({height[i],1,i});
        }
    }
    while(true) {
        bool f = false;
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) f = true;
        }
        if(!f) break;
        vector<array<int,3>>q1 = tmp1,q2 = tmp2;
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) {
                int mid = (l[i]+r[i])/2;
                q1.push_back({mid,0,i});
                q2.push_back({mid,0,i});
            }
        }
        sort(q1.rbegin(),q1.rend());
        sort(q2.begin(),q2.end());
        vector<int>mx1(n),mx2(n);
        DuelSegmentTree s1(n),s2(n);
        {
            for(int i = 0; i < q1.size(); i++) {
                if(q1[i][1] == 1) {
                    int id = q1[i][2];
                    s1.update(left[id],right[id]+1,id);
                }
                else {
                    mx1[q1[i][2]] = s1.query(q1[i][2]);
                }
            }
        }
        {
            for(int i = 0; i < q2.size(); i++) {
                if(q2[i][1] == 1) {
                    int id = q2[i][2];
                    s2.update(left[id],right[id]+1,id);
                }
                else {
                    mx2[q2[i][2]] = s2.query(q2[i][2]);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(l[i]+1 < r[i]) {
                int mid = (l[i]+r[i])/2;
                if(mx2[i] < mx1[i]) {
                    l[i] = mid;
                }
                else {
                    r[i] = mid;
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        finalHeight[i] = l[i];
    }
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:142:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             for(int i = 0; i < q1.size(); i++) {
      |                            ~~^~~~~~~~~~~
wall.cpp:153:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for(int i = 0; i < q2.size(); i++) {
      |                            ~~^~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39