Submission #230538

#	Time	Username	Problem	Language	Result	Execution time	Memory
230538		derrick20	Sails (IOI07_sails)	Java	90 / 100	1016 ms	56748 KiB

sails

/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class sails {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        Mast[] masts = new Mast[N];
        for (int i = 0; i < N; i++) {
            int h = sc.nextInt();
            int s = sc.nextInt();
            masts[i] = new Mast(h, s);
        }
        Arrays.sort(masts);

        TreeMap<Integer, Integer> deltas = new TreeMap<>();
        deltas.put(0, 1);
        deltas.put(masts[0].s, -1);
        for (int i = 1; i < N; i++) {
            int currH = masts[i].h;
            int sails = masts[i].s;
            int pos = currH - sails;
            if (deltas.containsKey(pos)) {
                // then it's a simple add 1
                deltas.merge(pos, 1, Integer::sum);
                if (deltas.get(pos) == 0) {
                    deltas.remove(pos);
                }
                deltas.merge(currH, -1, Integer::sum);
                if (deltas.get(currH) == 0) {
                    deltas.remove(currH);
                }
            }
            else {
                // see if the next higher exists.
                if (deltas.higherKey(pos) != null) {
                    int next = deltas.higherKey(pos);
                    deltas.merge(next, 1, Integer::sum);
                    if (deltas.get(next) == 0) {
                        deltas.remove(next);
                    }
                    deltas.merge(currH, -1, Integer::sum);
                    if (deltas.get(currH) == 0) {
                        deltas.remove(currH);
                    }
                    sails -= currH - next;
                }
                // now, we simplify into the same case.
                // We need to squeeze this extra overhang onto
                // the left side of the previous interval
                int prev = deltas.lowerKey(pos);
                deltas.merge(prev, 1, Integer::sum);
                if (deltas.get(prev) == 0) {
                    deltas.remove(prev);
                }
                deltas.merge(prev + sails, -1, Integer::sum);
                if (deltas.get(prev + sails) == 0) {
                    deltas.remove(prev + sails);
                }
            }
//            System.out.println(deltas);
        }
        long[] thickness = new long[deltas.lastKey() + 1];
        // there are at most 10^5 masts, so thickness at most 10^5,
        // but we need to add the sum of contributions, which
        // is (t - 1) + ... + 1 = (t-1)t / 2
        long ans = 0;
        for (int i = 0; i < thickness.length; i++) {
            if (i > 0) {
                thickness[i] = thickness[i - 1];
            }
            if (deltas.containsKey(i)) {
                thickness[i] += deltas.get(i);
//                System.out.println(thickness[i - 1] + " became " + thickness[i]);
            }
            ans += (thickness[i] * (thickness[i] - 1)) / 2;
        }
//        System.out.println(deltas);
//        System.out.println(Arrays.toString(thickness));
        out.println(ans);
        out.close();
    }

    static class Mast implements Comparable<Mast> {
        int h; int s;
        public Mast(int hh, int ss) {
            h = hh; s = ss;
        }
        public int compareTo(Mast s2) {
            return h - s2.h;
        }
        public String toString() {
            return "(" + h + ", " + s + ")";
        }
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}

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