import java.io.BufferedInputStream; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStream; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map.Entry; public class sia { private static int readInt(InputStream in) throws IOException { int ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1;) { if (c >= '0' && c <= '9') { dig = true; ret = ret * 10 + c - '0'; } else if (dig) { break; } } return ret; } private static long readLong(InputStream in) throws IOException { long ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1;) { if (c >= '0' && c <= '9') { dig = true; ret = ret * 10 + c - '0'; } else if (dig) { break; } } return ret; } public static void main(String[] args) throws IOException { class Pair { public Long ilosc; public Long ostatniaWysokosc; public Pair(Long ilosc, Long ostatniaWysokosc) { this.ilosc = ilosc; this.ostatniaWysokosc = ostatniaWysokosc; } } BufferedInputStream bis = new BufferedInputStream(System.in); int nPole = readInt(bis); // 1<= <= 500 000 int mSkoszenia = readInt(bis); // 1<= <= 500 000 HashMap<Long, Pair> trawa = new HashMap<Long, Pair>(nPole); // szybkoscWzrostu, ilosc, ostatniaWysokosc - potrzeba trzymania // poprzedniego dnia for (int i = 0; i < nPole; i++) { long lTmp = readInt(bis); if (trawa.containsKey(lTmp)) { (trawa.get(lTmp).ilosc)++; } else { Pair pair = new Pair(1l, 0l); trawa.put(lTmp, pair); } } LinkedHashMap<Long, Long> koszenia = new LinkedHashMap<Long, Long>(); // dzien, doIlu for (int i = 0; i < mSkoszenia; i++) { long fTmp = readLong(bis); long sTmp = readLong(bis); koszenia.put(fTmp, sTmp); } bis.close(); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out), 512); long before = 0; long ileSiana = 0; for (Entry<Long, Long> skos : koszenia.entrySet()) { long iloscDni = skos.getKey() - before; for (Entry<Long, Pair> ar : trawa.entrySet()) { long wysokoscNow = iloscDni * ar.getKey() + ar.getValue().ostatniaWysokosc; ileSiana += (wysokoscNow > skos.getValue() ? ar.getValue().ilosc * (wysokoscNow - skos.getValue()) : 0); ar.getValue().ostatniaWysokosc = skos.getValue(); } before = skos.getKey(); out.write("" + ileSiana + '\n'); ileSiana = 0; } out.close(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | import java.io.BufferedInputStream; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStream; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map.Entry; public class sia { private static int readInt(InputStream in) throws IOException { int ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1;) { if (c >= '0' && c <= '9') { dig = true; ret = ret * 10 + c - '0'; } else if (dig) { break; } } return ret; } private static long readLong(InputStream in) throws IOException { long ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1;) { if (c >= '0' && c <= '9') { dig = true; ret = ret * 10 + c - '0'; } else if (dig) { break; } } return ret; } public static void main(String[] args) throws IOException { class Pair { public Long ilosc; public Long ostatniaWysokosc; public Pair(Long ilosc, Long ostatniaWysokosc) { this.ilosc = ilosc; this.ostatniaWysokosc = ostatniaWysokosc; } } BufferedInputStream bis = new BufferedInputStream(System.in); int nPole = readInt(bis); // 1<= <= 500 000 int mSkoszenia = readInt(bis); // 1<= <= 500 000 HashMap<Long, Pair> trawa = new HashMap<Long, Pair>(nPole); // szybkoscWzrostu, ilosc, ostatniaWysokosc - potrzeba trzymania // poprzedniego dnia for (int i = 0; i < nPole; i++) { long lTmp = readInt(bis); if (trawa.containsKey(lTmp)) { (trawa.get(lTmp).ilosc)++; } else { Pair pair = new Pair(1l, 0l); trawa.put(lTmp, pair); } } LinkedHashMap<Long, Long> koszenia = new LinkedHashMap<Long, Long>(); // dzien, doIlu for (int i = 0; i < mSkoszenia; i++) { long fTmp = readLong(bis); long sTmp = readLong(bis); koszenia.put(fTmp, sTmp); } bis.close(); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out), 512); long before = 0; long ileSiana = 0; for (Entry<Long, Long> skos : koszenia.entrySet()) { long iloscDni = skos.getKey() - before; for (Entry<Long, Pair> ar : trawa.entrySet()) { long wysokoscNow = iloscDni * ar.getKey() + ar.getValue().ostatniaWysokosc; ileSiana += (wysokoscNow > skos.getValue() ? ar.getValue().ilosc * (wysokoscNow - skos.getValue()) : 0); ar.getValue().ostatniaWysokosc = skos.getValue(); } before = skos.getKey(); out.write("" + ileSiana + '\n'); ileSiana = 0; } out.close(); } } |