| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40168 |
2018-01-28T20:20:40 Z |
alanm |
Plahte (COCI17_plahte) |
C++14 |
|
614 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 + 1,i + n},{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);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
21488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
22868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
307 ms |
39380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
614 ms |
55384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
571 ms |
54580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
