Submission #170448

#	Time	Username	Problem	Language	Result	Execution time	Memory
170448		impetus_	Sunčanje (COCI18_suncanje)	C++14	0 / 130	4113 ms	206148 KiB

suncanje

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>     
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
//#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
//#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)4e5 + 10;
const int mod = (int)1e9 + 7;
 
#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 


int n, x1[maxn / 4], x2[maxn / 4], y11[maxn / 4], y2[maxn / 4], a, b, t[4][maxn], M;
vi vals;

inline void upd(int type, int pos, int val){
  for(; pos < M; pos |= (pos + 1))
    t[type][pos] += val;
}
inline int get(int type, int r){
  int res = 0;
  for(; r >= 0; r = (r & (r + 1)) - 1)
    res += t[type][r];
  return res;
}
inline int get(int type, int l, int r){
  return get(type, r) - get(type, l - 1);
} 

struct node{
  node *l, *r;
  int pr, sz, key, lz;
  node(){
    l = r = NULL;
    pr = sz = key = lz = 0;
  }
  node (int _key){
    key = _key;
    l = r = NULL;
    sz = 1;
    lz = 0;
    pr = uniform_int_distribution<>(0, inf)(rng);
  }
};

typedef node* pnode;

pnode root[4][maxn];

inline int sz(pnode t) {
  return t ? t->sz : 0;
}

inline pnode copy(pnode t) {
  return new node(t->key);
}

inline void upd_sz(pnode &t) {
  if(t)
    t->sz = sz(t->l) + 1 + sz(t->r);
} 
void split(pnode t, pnode &l, pnode &r, int key) {
  if(!t){
    r = l = NULL;
    return;
  }
  if(t -> key <= key)
    split(t -> r, t -> r, r, key), l = t;
  else
    split(t -> l, l, t -> l, key), r = t;
  upd_sz(l);
  upd_sz(r);
} 

void merge(pnode &t, pnode l, pnode r) {
  if(!l || !r)
    t = l ? l : r;
  else if(l -> pr > r -> pr)
    merge(l -> r, l -> r, r), t = l;
  else
    merge(r -> l, l, r -> l), t = r;
  upd_sz(t);
}

inline void insert(pnode &t1, pnode t2){
  pnode tl, tr;
  split(t1, tl, tr, t2 -> key);
  merge(tl, tl, copy(t2));
  merge(t1, tl, tr);
}
int get(pnode &t, int key) {
  if(t == NULL) return 0;
  pnode cur1, cur2;
  split(t, cur1, cur2, key);
  int res = sz(cur1);
  merge(t, cur1, cur2);
  return res;  
}   
inline void add(int type, int x, int y, int val){
  for(; x < M; x |= (x + 1)){
    insert(root[type][x], new node(y)); 
  }   
}    
inline int Sum(int type, int x, int y){
  int res = 0;
  for(; x >= 0; x = (x & (x + 1)) - 1)
    res += get(root[type][x], y);
  return res; 
} 
ll bad[maxn];

int R() {
    char c;
    int ans = 0;
    bool started = 0, is_negative = 0;
 
    while (true) {
        c = getchar();
        if ((c < '0' || c > '9') && c != '-' && !started) continue;
        if ((c < '0' || c > '9') && c != '-' && started) break;
        if (started) 
            ans = ans * 10;
 
        started = 1;
        if (c == '-') is_negative = 1;
        else ans += c - '0';
    }
 
    if (is_negative) 
      ans = -ans;
    return ans;
}
 

inline void solve () {
  n = R();
  forn(i, 1, n){
    x1[i] = R(); y11[i] = R();
    x2[i] = x1[i] + R();
    y2[i] = y11[i] + R();
    vals.pb(x1[i]);
    vals.pb(x2[i]);
    vals.pb(y11[i]);
    vals.pb(y2[i]);
  }  
  sort(all(vals));
  vals.resize(unique(all(vals)) - vals.begin());
  M = vals.size();
  forn(i, 0, maxn - 1)
    root[0][i] = root[1][i] = root[2][i] = root[3][i] = NULL;
  forn(i, 1, n){
    x1[i] = lower_bound(all(vals), x1[i]) - vals.begin();
    x2[i] = lower_bound(all(vals), x2[i]) - vals.begin();
    y11[i] = lower_bound(all(vals), y11[i]) - vals.begin();
    y2[i] = lower_bound(all(vals), y2[i]) - vals.begin();
  }
  forev(i, n, 1){
    int c1 = get(0, x2[i] + 1, M - 1);
    int c2 = get(1, y2[i] + 1, M - 1);
    int c4 = get(2, x1[i] - 1);
    int c5 = get(3, y11[i] - 1);
    upd(0, x1[i], 1);
    upd(1, y11[i], 1);
    upd(2, x2[i], 1);
    upd(3, y2[i], 1);
    ll cur = c1 + c2 + c4 + c5;
    cur -= Sum(0, x1[i] - 1, y11[i] - 1);
    add(0, x2[i], y2[i], 1);
    cur -= Sum(1, M - x2[i] - 2, M  - y2[i] - 2);
    add(1, M - x1[i] - 1, M - y11[i] - 1, 1);
    cur -= Sum(2, M - x2[i] - 2, y11[i] - 1);
    add(2, M - x1[i] - 1, y2[i], 1);
    cur -= Sum(3, x1[i] - 1, M - y2[i] - 2);
    add(3, x2[i], M - y11[i] - 1, 1);
    bad[i] = cur;
  }
  forn(i, 1, n){
    puts(bad[i] == n - i ? "YES" : "NO");
  } 
}
int main () {
  int tt = 1;
  //cin >> tt;
  forn(i, 1, tt)
    solve();  
}                                                                

Compilation message (stderr)

suncanje.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13