oj.uz

Submission #40169

# Submission time Handle Problem Language Result Execution time Memory
40169 2018-01-28T20:40:52 Z alanm Plahte (COCI17_plahte) C++14
160 / 160
 559 ms 55384 KB 
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <math.h>
#include <stack>
#include <limits.h>
#include <queue>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>
#include <deque>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#include <fstream>
#define REP(i,N)for(long long i=0;i<(N);i++)
#define FOR(i,a,b)for(long long i=(a);i<=(b);i++)
#define FORD(i,a,b)for(long long i=a;i>=(b);i--)
#define ll long long
#define vi vector<ll>
#define vii vector<pair<ll,ll> >
#define vvi vector<vector<ll> >
#define vb vector<bool>
#define pii pair<ll,ll>
#define ALL(x) (x).begin(), (x).end()
#define SZ(a)((ll)(a).size())
#define CHECK_BIT(n,x)((bool)((n)&(((ll)1)<<(x))))
#define pow2(x) ((x)*(x))
#define VELA 2000000009999999999ll
#define X first
#define Y second
#define DBG(x) //cerr<<#x<<" = "<<x<<"\n";
using namespace std;

struct Fenwick{
	vi tree;
	ll f(ll x) { return (x&(-x)); }
	Fenwick(ll n) { tree = vi(n+5,0ll); }
	void Add(ll k, ll val) {
		k++;
		for (;k <SZ(tree);k += f(k))tree[k] += val;
	}
	ll Get(ll k) {
		k++;
		ll res = 0;
		for (;k >0;k -= f(k))res += tree[k];
		return res;
	}
	ll Get(ll a, ll b) {
		return Get(b) - Get(a - 1);
	}
};

vvi graf;
vi color;
vi shots;
set<ll>* DFS(ll v) {
	set<ll>* curr=NULL;
	REP(i, SZ(graf[v])) {
		if (i == 0)
			curr = DFS(graf[v][i]);
		else {
			set<ll>* tmp=DFS(graf[v][i]);
			if (SZ(*tmp) > SZ(*curr))swap(curr, tmp);
			for (auto it = tmp->begin();it != tmp->end();it++)
				curr->insert(*it);
		}
	}
	if (SZ(graf[v])==0) {
		curr = new set<ll>();
		if(color[v]!=-1)
			curr->insert(color[v]);
	}
	shots[v] = SZ(*curr);
	return curr;
}

int main() {
	//cin.sync_with_stdio(0);
	ll n, m;
	scanf("%lld%lld", &n, &m);
	vi ycords;
	vector<pair<pii, pii>> events;
	REP(i, n) {
		ll x1, y1, x2, y2;
		scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
		ycords.push_back(y1);
		ycords.push_back(y2);
		events.push_back({ {x1,i+1000000},{y1,-y2} });
		events.push_back({ {x2 + 1,i},{y1,-y2} });
	}
	color = vi(m+n,-1);
	REP(i, m) {
		ll x, y, k;
		scanf("%lld%lld%lld", &x, &y, &k);
		ycords.push_back(y);
		color[i+n] = k;
		events.push_back({ {x,i + n+2000000},{y,-y} });
	}
	sort(ALL(events));

	sort(ALL(ycords));
	ll nYcords = 0;
	map<ll, ll> renamed;
	REP(i, SZ(ycords)) {
		if (i > 0 && ycords[i] != ycords[i - 1])nYcords++;
		renamed[ycords[i]] = nYcords + 1;
	}

	Fenwick is(SZ(renamed) + 5);
	vector<bool> was(n + m, false);
	vi kill_val(n + m, 0);
	graf=vvi(n + m);
	vector<bool> is_root(n,true);
	REP(i, SZ(events)) {
		ll y1 = renamed[events[i].Y.X], y2 = renamed[-events[i].Y.Y];
		ll typ = events[i].X.Y%1000000;
		if (i == 71)
			DBG("");
		if (was[typ]) {
			is.Add(y1, -kill_val[typ]);
			is.Add(y2 + 1, kill_val[typ]);
		}
		else {
			ll lst = is.Get(y2);
			lst--;
			if (lst != -1) {
				graf[lst].push_back(typ);
				if (typ < n)is_root[typ] = false;
			}
			if (typ < n) {//just rects
				kill_val[typ] = (typ)-(lst);
				is.Add(y1, kill_val[typ]);
				is.Add(y2 + 1, -kill_val[typ]);
			}
			DBG(lst);
		}
		was[typ] = true;
	}
	shots = vi(n + m,-1);
	REP(i,n) {
		if (is_root[i])
			DFS(i);
	}
	REP(i, n) {
		printf("%lld\n", shots[i]);
	}
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:86:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
                           ^
plahte.cpp:91:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
                                                ^
plahte.cpp:100:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &x, &y, &k);
                                    ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 21484 KB Output is correct
2 Correct 138 ms 22484 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 22868 KB Output is correct
2 Correct 181 ms 22776 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 39376 KB Output is correct
2 Correct 342 ms 37676 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 55384 KB Output is correct
2 Correct 558 ms 53352 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 54568 KB Output is correct
2 Correct 535 ms 52492 KB Output is correct
3 Correct 1 ms 2164 KB Output is correct