Submission #40169

#TimeUsernameProblemLanguageResultExecution timeMemory
40169alanmPlahte (COCI17_plahte)C++14
160 / 160
559 ms55384 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...