| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230538 |
2020-05-10T10:33:11 Z |
derrick20 |
Sails (IOI07_sails) |
Java 11 |
|
1000 ms |
56748 KB |
/**
* @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;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
16480 KB |
Output is correct |
| 2 |
Correct |
212 ms |
16136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
16056 KB |
Output is correct |
| 2 |
Correct |
209 ms |
16416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
243 ms |
16468 KB |
Output is correct |
| 2 |
Correct |
222 ms |
16308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
16652 KB |
Output is correct |
| 2 |
Correct |
238 ms |
16800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
18308 KB |
Output is correct |
| 2 |
Correct |
319 ms |
20052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
525 ms |
26096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
540 ms |
25688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
665 ms |
35356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
813 ms |
45396 KB |
Output is correct |
| 2 |
Correct |
765 ms |
50056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
886 ms |
49736 KB |
Output is correct |
| 2 |
Correct |
775 ms |
47044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
56748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
