| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230548 |
2020-05-10T10:50:44 Z |
derrick20 |
Sails (IOI07_sails) |
Java 11 |
|
1000 ms |
49972 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++) {
masts[i] = new Mast(sc.nextInt(), sc.nextInt());
}
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.
Integer next = deltas.higherKey(pos);
if (next != null) {
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;
Map.Entry<Integer, Integer> first = deltas.pollFirstEntry();
long thickness = first.getValue();
int curr = first.getKey();
while (deltas.size() > 0) {
first = deltas.pollFirstEntry();
int next = first.getKey();
ans += (next - curr) * (thickness * (thickness - 1)) / 2;
thickness += first.getValue();
curr = next;
}
// for (int i = 0; i <= deltas.lastKey(); i++) {
// if (deltas.containsKey(i)) {
// thickness += deltas.get(i);
//// System.out.println(thickness[i - 1] + " became " + thickness[i]);
// }
// ans += (thickness * (thickness - 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 |
217 ms |
17000 KB |
Output is correct |
| 2 |
Correct |
207 ms |
15812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
16280 KB |
Output is correct |
| 2 |
Correct |
222 ms |
16684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
234 ms |
16456 KB |
Output is correct |
| 2 |
Correct |
206 ms |
16416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
15928 KB |
Output is correct |
| 2 |
Correct |
244 ms |
16692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
255 ms |
18160 KB |
Output is correct |
| 2 |
Correct |
240 ms |
16504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
19880 KB |
Output is correct |
| 2 |
Correct |
526 ms |
24044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
588 ms |
25588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
671 ms |
34592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
803 ms |
38436 KB |
Output is correct |
| 2 |
Correct |
723 ms |
43092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
937 ms |
43928 KB |
Output is correct |
| 2 |
Correct |
822 ms |
43136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1110 ms |
49972 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
