Editing 2016 Jan Platinum Problem 2 Mowing the Field (section)

== Code ==

=== C++ ===
<pre>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int MAXN = 1 << 17;
const int MAXV = 1 << 30;

struct Node {
    int val;
    Node* child[2];

    Node() : val(0), child{nullptr, nullptr} {}

    Node* get_child(int c) {
        if (!child[c]) {
            child[c] = new Node;
        }
        return child[c];
    }

    void add(int x, int v, int lo, int hi) {
        val += v;
        if (hi - lo == 1) {
            return;
        }
        int mid = (lo + hi) / 2;
        if (x < mid) {
            get_child(0)->add(x, v, lo, mid);
        } else {
            get_child(1)->add(x, v, mid, hi);
        }
    }

    int query(int a, int b, int lo, int hi) {
        if (a <= lo && hi <= b) {
            return val;
        } else if (hi <= a || b <= lo) {
            return 0;
        }
        int mid = (lo + hi) / 2;
        return (child[0] ? child[0]->query(a, b, lo, mid) : 0) +
               (child[1] ? child[1]->query(a, b, mid, hi) : 0);
    }
};

vector<Node> bit(MAXN);

// Logically executes array[y].add(x, v) += v.
void bit_add(int x, int y, int v) {
    for(unsigned j = y | MAXN; j < (MAXN << 1); j += j & -j) {
        bit[j ^ MAXN].add(x, v, 0, MAXV);
    }
}

// Returns the sum of array[i].query(x0, x1) for 0 <= i < y
int bit_get(int x0, int x1, int y) {
    int ret = 0;
    for(int j = y - 1; y != 0; j &= j - 1) {
        ret += bit[j].query(x0, x1, 0, MAXV);
        if (!j) break;
    }
    return ret;
}

int main() {
    // Replace this with the actual file path
    freopen("mowing.in", "r", stdin);
    freopen("mowing.out", "w", stdout);

    ios_base::sync_with_stdio(false);

    int N; cin >> N;
    int T; cin >> T;
    vector<pair<int, int> > cells(N);
    for (int i = 0; i < N; i++) {
        cin >> cells[i].first >> cells[i].second;
    }

    // Will fill this section after explaining the approach

    return 0;
}

</pre>

=== Java ===
<pre>
import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 1 << 17;
    static final int MAXV = 1 << 30;
    
    static class Node {
        int val;
        Node[] child = new Node[2];
        
        Node() {
            this.val = 0;
        }
        
        Node get_child(int c) {
            if (child[c] == null) {
                child[c] = new Node();
            }
            return child[c];
        }
        
        void add(int x, int v, int lo, int hi) {
            val += v;
            if (hi - lo == 1) {
                return;
            }
            int mid = (lo + hi) / 2;
            if (x < mid) {
                get_child(0).add(x, v, lo, mid);
            } else {
                get_child(1).add(x, v, mid, hi);
            }
        }
        
        int query(int a, int b, int lo, int hi) {
            if (a <= lo && hi <= b) {
                return val;
            } else if (hi <= a || b <= lo) {
                return 0;
            }
            int mid = (lo + hi) / 2;
            return (child[0] != null ? child[0].query(a, b, lo, mid) : 0) +
                   (child[1] != null ? child[1].query(a, b, mid, hi) : 0);
        }
    }
    
    static Node[] bit = new Node[MAXN];

    // Logically executes array[y].add(x, v) += v.
    static void bit_add(int x, int y, int v) {
        for(int j = y | MAXN; j < (MAXN << 1); j += j & -j) {
            bit[j ^ MAXN].add(x, v, 0, MAXV);
        }
    }

    // Returns the sum of array[i].query(x0, x1) for 0 <= i < y
    static int bit_get(int x0, int x1, int y) {
        int ret = 0;
        for(int j = y - 1; y != 0; j &= j - 1) {
            ret += bit[j].query(x0, x1, 0, MAXV);
            if (j == 0) break;
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("mowing.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("mowing.out")));
        
        int N = Integer.parseInt(br.readLine());
        int T = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < N; i++) {
            // Read in the pairs and store in an appropriate data structure
            // Will need to implement the rest of the solution here
        }

        // Close the input/output streams
        br.close();
        pw.close();
    }
}

</pre>

=== Python ===
<pre>
import sys
from collections import defaultdict

MAXN = 1 << 17
MAXV = 1 << 30

class Node:
    def __init__(self):
        self.val = 0
        self.child = [None, None]

    def get_child(self, c):
        if self.child[c] is None:
            self.child[c] = Node()
        return self.child[c]

    def add(self, x, v, lo, hi):
        self.val += v
        if hi - lo == 1:
            return
        mid = (lo + hi) // 2
        if x < mid:
            self.get_child(0).add(x, v, lo, mid)
        else:
            self.get_child(1).add(x, v, mid, hi)

    def query(self, a, b, lo, hi):
        if a <= lo and hi <= b:
            return self.val
        elif hi <= a or b <= lo:
            return 0
        mid = (lo + hi) // 2
        return (self.child[0].query(a, b, lo, mid) if self.child[0] else 0) + \
               (self.child[1].query(a, b, mid, hi) if self.child[1] else 0)


bit = defaultdict(Node)

def bit_add(x, y, v):
    j = y | MAXN
    while j < (MAXN << 1):
        bit[j ^ MAXN].add(x, v, 0, MAXV)
        j += j & -j

def bit_get(x0, x1, y):
    ret = 0
    j = y - 1
    while j != 0:
        ret += bit[j].query(x0, x1, 0, MAXV)
        j &= j - 1
        if j == 0:
            break
    return ret

def main():
    # Reads input, processes it, and writes output.
    # Implementation needed here.

if __name__ == "__main__":
    main()

</pre>


[[Category:Yearly_2015_2016]]
[[Category:Platinum]]
[[Category:Geometry]]
[[Category:Segment Tree]]
[[Category:Sweep Line]]