Submission #50900

#	Time	Username	Problem	Language	Result	Execution time	Memory
50900		polyfish	New Home (APIO18_new_home)	C++14	0 / 100	5081 ms	158144 KiB

new_home

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "new-home"
#define y1 __y1
#define y2 __y2

const int blockSize = 900;
const int MAX_N = 300002;
const int INF = 1e9;

struct rect {
    int x1, x2, y1, y2, val;

    rect() {}
    rect(int _x1, int _x2, int _y1, int _y2, int _val) {
        x1 = min(_x1, _x2); x2 = max(_x1, _x2);
        y1 = min(_y1, _y2), y2 = max(_y1, _y2);
        val = _val;
    }
};

struct query {
    int x, y, id;

    query() {}
    query(int x, int y, int id):
        x(x), y(y), id(id) {}
    bool operator<(const query & p) {
        return x<p.x;
    }
};

struct store {
    int x, a, b;

    store() {}
    store(int x, int a, int b):
        x(x), a(a), b(b) {}

    bool operator<(const store &p) {
        return x<p.x;
    }
};

int n, nType, nQuery, nVal, nBlock=1, xMin[500], xMax[500], ps[MAX_N*3];
int res[MAX_N], res1[MAX_N], res2[MAX_N];
query q[MAX_N];
vector<store> storeType[MAX_N];
vector<query> block[500];
vector<rect> rectLeft, rectRight;
vector<pair<int, int> > tmp;
map<int, int> compVal;

struct node {
	int a, b, x;

	node() {}
	node(int a, int b, int x):
		a(a), b(b), x(x) {}

	bool operator<(const node &p) const {
		return b<p.b;
	}

	bool operator>(const node &p) const {
        return b>p.b;
	}
};

struct rmq_node {
	pair<node, node> tr[MAX_N*4];
	int sizeOfTree;

	void init(int _size) {
		sizeOfTree = _size;
		for (int i=0; i<=4*_size; ++i)
			tr[i].first = tr[i].second = node(-1, -1, -1);
	}

	void upd(int pos, node val, int l, int r, int id) {
		if (pos<l || pos>r)
			return;
		if (l==pos && pos==r) {
			tr[id].first = tr[id].second = val;
			return;
		}
		int mid = (l + r) / 2;
		upd(pos, val, l, mid, id*2);
		upd(pos, val, mid+1, r, id*2+1);
		if (tr[id*2].first.x==-1)
			tr[id] = tr[id*2+1];
		else if (tr[id*2+1].first.x==-1)
			tr[id] = tr[id*2];
		else {
			tr[id].first = max(tr[id*2].first, tr[id*2+1].first);
			tr[id].second = min(tr[id*2].second, tr[id*2+1].second);
		}
	}

	node getMax(int u, int v, int l, int r, int id) {
		if (v<l || u>r)
			return node(-1, -1, -1);
		if (u<=l && r<=v)
			return tr[id].first;
		int mid = (l + r) / 2;
		node L = getMax(u, v, l, mid, id*2);
		node R = getMax(u, v, mid+1, r, id*2+1);
		if (L.x==-1)
			return R;
		if (R.x==-1)
			return L;
		return max(L, R);
	}

	node getMin(int u, int v, int l, int r, int id) {
		if (v<l || u>r)
			return node(-1, -1, -1);
		if (u<=l && r<=v)
			return tr[id].second;
		int mid = (l + r) / 2;
		node L = getMin(u, v, l, mid, id*2);
		node R = getMin(u, v, mid+1, r, id*2+1);
		if (L.x==-1)
			return R;
		if (R.x==-1)
			return L;
		return min(L, R);
	}

	void upd(int pos, node val) {
		upd(compVal[pos], val, 1, sizeOfTree, 1);
	}

	node getMax(int u, int v) {
		return getMax(u, v, 1, sizeOfTree, 1);
	}

	node getMin(int u, int v) {
		return getMin(u, v, 1, sizeOfTree, 1);
	}
} tr;

struct vertex {
    int val, lazy;
    vertex *L, *R;

    vertex() {
        val = lazy = -INF;
        L = NULL; R = NULL;
    }

    void createChild() {
        if (L==NULL) {
            L = new vertex();
            R = new vertex();
        }
    }
};

struct dynamicSegmenTree {
    vertex *root;

    void init() {
        root = new vertex();
    }

    void down(vertex *u) {
        u->createChild();
        vertex *v1 = u->L, *v2 = u->R;
        v1->val = max(v1->val, u->lazy);
        v1->lazy = max(v1->lazy, u->lazy);
        v2->val = max(v2->val, u->lazy);
        v2->lazy = max(v2->lazy, u->lazy);
        u->lazy = -INF;
    }

    void upd(int u, int v, int val, int l, int r, vertex *cur) {
        if (v<l || u>r)
            return;
        if (u<=l && r<=v) {
            cur->val = max(cur->val, val);
            cur->lazy = max(cur->lazy, val);
            return;
        }
        down(cur);
        int mid = (l + r) / 2;
        cur->createChild();
        upd(u, v, val, l, mid, cur->L);
        upd(u, v, val, mid+1, r, cur->R);
        cur->val = max(cur->L->val, cur->R->val);
    }

    int get(int pos, int l, int r, vertex *cur) {
        if (pos<l || pos>r)
            return -INF;
        if (pos==l && r==pos)
            return cur->val;
        down(cur);
        cur->createChild();
        int mid = (l + r) / 2;
        return max(get(pos, l, mid, cur->L),
                   get(pos, mid+1, r, cur->R));
    }

    void upd(int u, int v, int val) {
        upd(u, v, val, 1, INF, root);
    }

    int get(int pos) {
        return get(pos, 1, INF, root);
    }
} T[500];

void enter() {
	cin >> n >> nType >> nQuery;
	for (int i=1; i<=n; ++i) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		storeType[t].push_back(store(x, a, b));
	}
	for (int i=1; i<=nQuery; ++i) {
		cin >> q[i].x >> q[i].y;
		q[i].id = i;
	}
}

void compress() {
	vector<int> container;
	container.push_back(1);
	for (int i=1; i<=nType; ++i) {
        for (int j=0; j<storeType[i].size(); ++j) {
            container.push_back(storeType[i][j].a);
            container.push_back(storeType[i][j].b+1);
        }
	}
	for (int i=1; i<=nQuery; ++i)
        container.push_back(q[i].y);
	sort(container.begin(), container.end());
	for (int i=0; i<container.size(); ++i) {
		if (i==0 || container[i]!=container[i-1])
			++nVal;
		compVal[container[i]] = nVal;
	}
}

void init_store(int id, bool leftside, vector<rect> &queryContainer) {
	tr.init(nVal);
	sort(storeType[id].begin(), storeType[id].end());
	int t = -1;
	if (leftside) {
		reverse(storeType[id].begin(), storeType[id].end());
		t *= -1;
        tr.upd(1, node(1, INF, -2*INF));
	}
	else {
        tr.upd(1, node(1, INF, 2*INF));
	}
	for (int i=(int)storeType[id].size()-1; i>=0; --i) {
		int a = storeType[id][i].a, b = storeType[id][i].b, x = storeType[id][i].x;
		node L = tr.getMax(compVal[a], compVal[b]);
		node R = tr.getMax(1, compVal[a]);
		if (R.b>=b) {
			queryContainer.push_back(rect(x, (x+R.x+leftside)/2, a, b, t*x));
			tr.upd(R.a, node(R.a, a-1, R.x));
			tr.upd(b+1, node(b+1, R.b, R.x));
			tr.upd(a, node(a, b, x));
			continue;
		}
		if (R.b>=a) {
			queryContainer.push_back(rect(x, (R.x+x+leftside)/2, a, R.b, t*x));
			tr.upd(R.a, node(R.a, a-1, R.x));
		}
		if (L.b>=b) {
			queryContainer.push_back(rect(x, (x+L.x+leftside)/2, b, L.a, t*x));
			tr.upd(b+1, node(b+1, L.b, L.x));
		}
		while (true) {
			node M = tr.getMin(compVal[a], compVal[b]);
			if (M.x==-1)
				break;
			queryContainer.push_back(rect(x, (x+M.x+leftside)/2, M.a, M.b, t*x));
			tr.upd(M.a, node(-1, -1, -1));
		}
		tr.upd(a, node(a, b, x));
	}
}

void add_invalid_year(int id) {
    tmp.clear();
    for (int i=0; i<storeType[id].size(); ++i) {
        tmp.push_back(make_pair(compVal[storeType[id][i].a], 1));
        tmp.push_back(make_pair(compVal[storeType[id][i].b+1], -1));
    }
    sort(tmp.begin(), tmp.end());
    int cnt = 0;
    for (int i=0; i+1<tmp.size(); ++i) {
        cnt += tmp[i].second;
        if (cnt>0) {
            ps[tmp[i].first]++;
            ps[tmp[i+1].first]--;
        }
    }
}

void sqrt_decomposition() {
	for (int i=1; i<=nQuery; ++i) {
		block[nBlock].push_back(q[i]);
		if (i<=n && i%blockSize==0)
			++nBlock;
	}
	for (int i=1; i<=nBlock; ++i) {
		sort(block[i].begin(), block[i].end());
		xMin[i] = block[i][0].x;
		xMax[i] = block[i].back().x;
	}
}

void process_query(vector<rect> r, int res[]) {
	for (int i=1; i<=nBlock; ++i)
		T[i].init();
    for (int i=1; i<=nQuery; ++i)
        res[i] = -INF;
	for (int i=0; i<r.size(); ++i) {
		int x1 = r[i].x1, x2 = r[i].x2;
		int y1 = r[i].y1, y2 = r[i].y2;
		int val = r[i].val;
		for (int j=1; j<=nBlock; ++j) {
            if (xMin[j]>x2 || xMax[j]<x1)
                continue;
            if (x1<=xMin[j] && xMax[j]<=x2) {
                T[j].upd(y1, y2, val);
            }
            else {
                for (int k=0; k<block[j].size(); ++k)
                    if (x1<=block[j][k].x && block[j][k].x<=x2
                        && y1<=block[j][k].y && block[j][k].y<=y2)
                        res[block[j][k].id] = max(res[block[j][k].id], val);
            }
		}
	}
    for (int i=1; i<=nBlock; ++i) {
        for (int j=0; j<block[i].size(); ++j) {
            res[block[i][j].id] = max(res[block[i][j].id], T[i].get(block[i][j].y));
        }
    }
}

int main() {
	//freopen(FILE_NAME".inp", "r", stdin);
	//freopen(FILE_NAME".out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	compress();
	for (int i=1; i<=nType; ++i) {
		init_store(i, false, rectRight);
		init_store(i, true, rectLeft);
        add_invalid_year(i);
	}
	for (int i=1; i<=nVal; ++i)
        ps[i] += ps[i-1];
	sqrt_decomposition();
	process_query(rectRight, res1);
	process_query(rectLeft, res2);
    for (int i=1; i<=nQuery; ++i) {
        int x = q[i].x, y = q[i].y, id = q[i].id;
        if (ps[compVal[y]]!=nType)
            res[id] = -1;
        else
            res[id] = max(x+res1[id], res2[id]-x);
    }
    for (int i=1; i<=nQuery; ++i) {
        cout << max(-1, res[i]) << '\n';
    }
}

Compilation message (stderr)

new_home.cpp: In function 'void compress()':
new_home.cpp:236:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<storeType[i].size(); ++j) {
                       ~^~~~~~~~~~~~~~~~~~~~
new_home.cpp:244:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<container.size(); ++i) {
                ~^~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void add_invalid_year(int)':
new_home.cpp:295:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<storeType[id].size(); ++i) {
                   ~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:301:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i+1<tmp.size(); ++i) {
                   ~~~^~~~~~~~~~~
new_home.cpp: In function 'void process_query(std::vector<rect>, int*)':
new_home.cpp:326:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=nQuery; ++i)
     ^~~
new_home.cpp:328:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=0; i<r.size(); ++i) {
  ^~~
new_home.cpp:328:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<r.size(); ++i) {
                ~^~~~~~~~~
new_home.cpp:339:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int k=0; k<block[j].size(); ++k)
                               ~^~~~~~~~~~~~~~~~
new_home.cpp:347:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<block[i].size(); ++j) {
                       ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20