Cod sursa(job #613686)

Utilizator floringh06Florin Ghesu floringh06 Data 3 octombrie 2011 23:36:13
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.15 kb
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 100005
#define x first
#define y second

vi arb[MAX_N << 2];
vi sqy[MAX_N << 2];

pii P[MAX_N];
int X1, X2, Y1, Y2, N, cost[MAX_N];
int vl[MAX_N], vr[MAX_N], tmp[MAX_N];
int RES;

void merge (int node, int li, int lf) {
     arb[node].resize(lf - li + 1);
     sqy[node].resize(lf - li + 1);
     
     int sl = 2*node;
     int sr = 2*node + 1;
     
     arb[sl].pb(oo), arb[sr].pb(oo);
     
     FOR (i, 0, sz(sqy[sl])) vl[i] = (i > 0) ? sqy[sl][i] - sqy[sl][i - 1] : sqy[sl][i];
     FOR (i, 0, sz(sqy[sr])) vr[i] = (i > 0) ? sqy[sr][i] - sqy[sr][i - 1] : sqy[sr][i];
     
     int i, j, k;
     for (i = 0, j = 0, k = 0; k <= lf - li; ++k)
         if (arb[sl][i] < arb[sr][j]) {
             arb[node][k] = arb[sl][i];
             tmp[k] = vl[i++];
         }
         else {
             arb[node][k] = arb[sr][j];
             tmp[k] = vr[j++];
         }
          
     sqy[node][0] = tmp[0];
     FOR (i, 1, lf - li + 1) sqy[node][i]= sqy[node][i - 1] + tmp[i];
}

void buildtree (int node, int li, int lf) {
     if (li == lf)  {
        arb[node].clear();
        sqy[node].clear();
        arb[node].pb(P[li].y);
        sqy[node].pb(cost[li]);
     }
     else {
          int m = (li + lf) >> 1;
          buildtree(2*node, li, m);
          buildtree(2*node + 1, m + 1, lf);
          
          merge(node, li, lf);
     }
}

int summify (int node) {
     if (arb[node][0] > Y2 || arb[node][sz(arb[node]) - 1] < Y1) return 0LL;
     
     int li, lf, m, c1, c2;
     li = 0, lf = sz(arb[node]) - 1;
     
     while (li <= lf) {
           m = (li + lf) >> 1;
           if (arb[node][m] < Y1) li = m + 1;
                             else lf = m - 1;
     }

     while (m && arb[node][m - 1] >= Y1) --m;
     while (arb[node][m] < Y1 && m < sz(arb[node]) - 1) ++m;
     c1 = m;

     li = 0, lf = sz(arb[node]) - 1;

     while (li <= lf) {
           m = (li + lf) >> 1;
           if (arb[node][m] < Y2) li = m + 1;
                             else lf = m - 1;
     }
     while (m < sz(arb[node]) - 1 && arb[node][m + 1] <= Y2) ++m;
     while (arb[node][m] > Y2 && m) --m;
     c2 = m;

     if (!c1)
         return sqy[node][c2];
     else
         return sqy[node][c2] - sqy[node][c1 - 1];
}

void query (int node, int li, int lf) {
     if (X1 <= P[li].x && P[lf].x <= X2)
        RES += summify (node);
     else 
          if (li != lf) {
             int m = (li + lf) >> 1;
             
             if (X1 <= P[m].x) 
                query(2*node, li, m);
             if (P[m + 1].x <= X2)
                query(2*node + 1, m + 1, lf);
          }
}

int main () {
    freopen ("zoo.in", "r", stdin);
    freopen ("zoo.out", "w", stdout);
    
    int tests = 1;
//    scanf ("%d", &tests);
    while (tests--) {
          scanf ("%d", &N);
          
          FOR (i, 0, N) {
              scanf ("%d %d", &P[i].x, &P[i].y);
              cost[i] = 1;
          }
          
          sort (P, P + N);
          buildtree(1, 0, N - 1);
              
          int nq;
          scanf ("%d", &nq);
          
          FOR (i, 0, nq) {
              scanf ("%d %d %d %d", &X1, &Y1, &X2, &Y2);
              
              RES = 0;
              query (1, 0, N - 1);
              
              printf ("%d\n", RES);
          }
    } 
    
    return 0;
}