Задание на Java

@Iqura · Регистрация: 22.10.2019

Студворк — интернет-сервис помощи студентам

Вот одна из задач Василька, которая уже две недели ему не поддается. Завтра у него День рождения! Давайте сделаем Вася интеллектуальный подарок - напишем быстрый код, который решит его проблему.

Итак, задается N строк, пронумерованных от 1 до N. Ваша программа должна Оператива ответить на Q запросов. Запрос имеет вид: l, r, S. Для каждого запроса программа должна найти, сколько раз строку S встретится на промежутке [l, r].

Входные данные

Первая строка содержит целое число N (1 <= N <= 100000) - количество строк.

Далее следуют N строк.

Следующая строка содержит Q (1 <= Q <= 100000) - количество запросов.

Далее идут строки с запросом: l, r, S (1 <= l <= r <= N).

Все строки имеют длину от 5 до 10 символов.

Выходные данные

Для каждого запроса в отдельном строки вывести ответ

Пример входных данных
3
abc
def
abc
3
1 2 abc
1 3 abc
1 2 hgj

Пример выходных данных

1
2
0
мой код

Java
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
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args){
        
        Scanner read = new Scanner(System.in);
        long a,d,e,b,zz=0;
        String z;
        a=read.nextLong();
        String[] q=new String[(int) a]; 
        for(int i=0;i<a;i++) {
            q[i]=read.next();
            
        }
        b=read.nextLong();
        for(int j=0;j<b;j++) {
            zz=0;
            d=read.nextLong();
            e=read.nextLong();
            z=read.next();
            for(int p=(int)d;p<=e;p++) {
                if(z.equals(q[p-1])) {
                    zz++;
                }
                
            }
            System.out.println(zz);
        }
        
    }
}

там лимит в 3 секунды, как ускорить программу?
TLE

@xoraxax · 16.12.2019, 17:32

лонги тебе зачем? лишние касты зачем? переменные нормально называй чо за zz? чо за b? код в тэги java заверни

@Iqura · 16.12.2019, 19:26 **[ТС]**

я не знаю что такое мертвые репликации, я просто имею код, который работает, но в некоторых тестах не проходит по времени.

@Auror · 16.12.2019, 19:34

Самый банальный способ придания ускорения - не использовать Сканнер. Это самый медленный способ. Хотя бы буффер ридер и инпутстримридер.

@sdasdaw · 16.12.2019, 21:56

Bash
1
2
3
1
2
0

Кликните здесь для просмотра всего текста

Java
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
import java.io.ByteArrayInputStream;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        System.setIn(new ByteArrayInputStream(
                ("3\n" +
                        "abc\n" +
                        "def\n" +
                        "abc\n" +
                        "3\n" +
                        "1 2 abc\n" +
                        "1 3 abc\n" +
                        "1 2 hgj")
                        .getBytes()));
 
        Scanner scn = new Scanner(System.in);
 
        String[] sources = new String[Integer.parseInt(scn.nextLine())];
        for (int i = 0; i < sources.length; i++) sources[i] = scn.nextLine();
 
        RoadMap map = new RoadMap(sources);
 
        int queries = scn.nextInt();
        for (int i = 0; i < queries; i++)
            System.out.println(map.getCount(
                    scn.nextInt() - 1,
                    scn.nextInt() - 1,
                    scn.nextLine()
            ));
    }
 
    static class RoadMap {
        HashMap<String, Encounter> flag;
 
        RoadMap(String[] sources) {
            flag = new HashMap<>();
 
            for (int i = 0; i < sources.length; i++) {
                if (flag.containsKey(sources[i])) flag.get(sources[i]).append(i);
                else flag.put(sources[i], new Encounter(i));
            }
        }
 
        int getCount(int start, int end, String flag) {
            Encounter tmp = this.flag.get(flag.substring(1));
 
            return tmp == null ?
                    0
                    :
                    tmp.getCount(start, end);
        }
    }
 
    static class Encounter {
        ArrayList<Integer> indexes;
 
        Encounter(int index) {
            indexes = new ArrayList<>();
            indexes.add(index);
        }
 
        void append(int i) {
            indexes.add(i);
        }
 
        int getCount(int start, int end) {
            /*int result = 0;
 
            for (Integer value : indexes) {
                if (value >= start && value <= end) result++;
                if (value >= end) break;
            }
 
            return result;*/
            int startEnc = indexes.indexOf(start);
            int endEnc = indexes.indexOf(end);
 
            return endEnc == -1 ?
                    indexes.size() - startEnc - 1
                    :
                    endEnc - startEnc + 1;
        }
    }
}

@korvin_ · 16.12.2019, 22:08

Не по теме:

Ой лол

@korvin_ · 16.12.2019, 23:37

sdasdaw, ты можешь лучше:

Java
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
import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.Consumer;
 
import static java.lang.System.lineSeparator;
import static java.lang.System.setOut;
 
final class Vasiliy {
 
    public static void main(String[] args) {
        //Sdasdaw.run(testInput());
        //Korvin.run(testInput());
        final byte[] benchInput = benchInput();
        measure(100, "Sdasdaw", Sdasdaw::run, benchInput);
        measure(100, "Korvin", Korvin::run, benchInput);
    }
 
    private static void measure(int runs, String title, Consumer<InputStream> proc, byte[] benchInput) {
        final var stdout = System.out;
        setOut(new PrintStream(PrintStream.nullOutputStream()));
        var min = Long.MAX_VALUE;
        var max = 0L;
        var tot = 0L;
        for (var i = 0; i < runs; i++) {
            final var input = new ByteArrayInputStream(benchInput);
            final var start = System.currentTimeMillis();
            proc.accept(input);
            final var end = System.currentTimeMillis();
            final var dur = end - start;
            min = Math.min(min, dur);
            max = Math.max(max, dur);
            tot += dur;
        }
        final var avg = tot / 1000.0 / runs;
        setOut(stdout);
        System.out.printf("%10s, %d run(s) took %8.3fs tot, %8.3fs avg, %8.3fs min, %8.3fs max%n",
                title, runs, tot / 1000.0, avg, min / 1000.0, max / 1000.0);
    }
 
    private static ByteArrayInputStream testInput() {
        return new ByteArrayInputStream(
                ("3\n" +
                        "abc\n" +
                        "def\n" +
                        "abc\n" +
                        "3\n" +
                        "1 2 abc\n" +
                        "1 3 abc\n" +
                        "1 2 hgj")
                        .getBytes());
    }
 
    private static byte[] benchInput() {
        final var input = new StringBuilder();
        final var n = 100_000;
        input.append(n).append(lineSeparator());
        for (int i = 0; i < n; i++) {
            input.append(randomString()).append(lineSeparator());
        }
        final var q = 100_000;
        input.append(q).append(lineSeparator());
        for (int i = 0; i < q; i++) {
            final var start = ThreadLocalRandom.current().nextInt(1, n / 2);
            final var end = ThreadLocalRandom.current().nextInt(start + 1, n + 1);
            input
                    .append(start).append(' ')
                    .append(end).append(' ')
                    .append(randomString()).append(lineSeparator());
        }
        return input.toString().getBytes();
    }
 
    private static String randomString() {
        final var n = ThreadLocalRandom.current().nextInt(5, 11);
        final var chars = new char[n];
        for (var i = 0; i < n; i++) {
            chars[i] = (char) ThreadLocalRandom.current().nextInt('a', 'z'+1);
        }
        return new String(chars);
    }
}

=>

Code
1
2
   Sdasdaw, 100 run(s) took   26.229s tot,    0.262s avg,    0.194s min,    0.558s max
    Korvin, 100 run(s) took    6.557s tot,    0.066s avg,    0.044s min,    0.241s max

Добавлено через 28 минут
sdasdaw, и ещё вот это объясни:

Java
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
import org.junit.Assert;
import org.junit.Test;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
 
public class SdasdawTest {
 
    @Test
    public void test() {
        final var in = new ByteArrayInputStream(
                ("4\n" +
                        "abc\n" +
                        "def\n" +
                        "abc\n" +
                        "hij\n" +
                        "3\n" +
                        "1 2 abc\n" +
                        "1 3 abc\n" +
                        "1 4 abc")
                        .getBytes());
        final var out = new ByteArrayOutputStream();
        final var stdout = System.out;
        System.setOut(new PrintStream(out));
        Sdasdaw.run(in);
        final var result = out.toString();
        System.setOut(stdout);
 
        Assert.assertEquals("1\n2\n2\n", result);
    }
}

=>

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
expected:<1
2
[2]
> but was:<1
2
[1]
>
 
org.junit.ComparisonFailure: expected:<1
2
[2]
> but was:<1
2
[1]

@sdasdaw · 17.12.2019, 01:20

korvin_, Немного поигрался

Bash
1
2
3
4
5
Sdasdaw-V1, 5 run(s) took    3.424s tot,    0.685s avg,    0.390s min,    1.236s max
Sdasdaw-V2, 5 run(s) took    0.772s tot,    0.154s avg,    0.121s min,    0.202s max
Sdasdaw-V3, 5 run(s) took    0.534s tot,    0.107s avg,    0.089s min,    0.133s max
Sdasdaw-V4, 5 run(s) took    0.528s tot,    0.106s avg,    0.084s min,    0.148s max
Sdasdaw-V5, 5 run(s) took    0.516s tot,    0.103s avg,    0.080s min,    0.143s max

v2 - без indexOf, substring, с bufferedReader
v3 - без HashMap
v4 - c проверкой конца
v5 - с бинарным поиском

@korvin_ · 17.12.2019, 10:22

sdasdaw, а тест-то проходят?

@sdasdaw · 17.12.2019, 10:37

korvin_, аа, конечно исправил (вроде как) (еще в самом начале)

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	16.12.2019, 17:32
	лонги тебе зачем? лишние касты зачем? переменные нормально называй чо за zz? чо за b? код в тэги java заверни 0

@Iqura 0 / 0 / 0 Регистрация: 22.10.2019 Сообщений: 2
	16.12.2019, 19:26 [ТС]
	я не знаю что такое мертвые репликации, я просто имею код, который работает, но в некоторых тестах не проходит по времени. 0

@Auror 115 / 79 / 40 Регистрация: 18.12.2015 Сообщений: 192
	16.12.2019, 19:34
	Самый банальный способ придания ускорения - не использовать Сканнер. Это самый медленный способ. Хотя бы буффер ридер и инпутстримридер. 0

@korvin_
	16.12.2019, 22:08
	Не по теме: Ой лол Миниатюры 0

@korvin_ 4575 / 2774 / 491 Регистрация: 28.04.2012 Сообщений: 8,764
	17.12.2019, 10:22
	sdasdaw, а тест-то проходят? 0

@sdasdaw 406 / 278 / 93 Регистрация: 14.03.2017 Сообщений: 777
	17.12.2019, 10:37
	korvin_, аа, конечно исправил (вроде как) (еще в самом начале) 0