For example:
16
9001 9001
8999 8999
9001 8999
8999 9001
-9001 -9001
-9001 -8999
-8999 -9001
-8999 -8999
9001 -9001
8999 -8999
9001 -8999
8999 -9001
-9001 9001
-8999 8999
-9001 8999
-8999 9001
5
9000 9000
9000 -9000
-9000 -9000
-9000 9000
0 0

My AC program gives answer:
1 2 3 4
9 10 11 12
5 6 7 8
13 14 15 16
2

But right answer:
1 2 3 4
9 10 11 12
5 6 7 8
13 14 15 16
2 8 10 14

 First I wrote the program in Java, but I got TLE on test #9, below is my program that gets TLE:

import java.util.Scanner;

public class Main {

    public static int read(int idx, int[] tree){
        int sum = 0;
        while(idx > 0){
            sum += tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    public static void update(int idx, int maxIndex, int[] tree){
        while(idx <= maxIndex){
            tree[idx]++;
            idx += idx & (-idx);
        }
    }

    public static void main(String[] args) {
        int N;
        int maxIndex = 32005;

        int[] level;
        int[] binaryIndexTree;

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        level = new int[N+1];
        binaryIndexTree = new int[maxIndex];

        for(int i=0; i<N; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            x++;
            level[ read(x, binaryIndexTree) ]++;
            update(x, maxIndex, binaryIndexTree);
        }
        for(int i=0; i<N; i++){
            System.out.println(level[i]);
        }

    }
}

Then I write in C++ and get AC?
@admins: Please extend time limit for Java.

my solution takes 0.031 seconds.

Can Anyone be kind enough to explain this ques to me? I'll be grateful to you..

DO your own solve then check this do not cheat yourself
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define FastAF ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v){for (auto &it : v) cin >> it;return istream;}
template <typename T> // cout << vector<T>
ostream &operator<<(ostream &ostream, const vector<T> &c){for (auto &it : c) cout << it << " ";return ostream;}

const int mx=2e5;

int ar[mx];
void d(){
    ar[0]=2;
    int k=1;
    for(int i=3;i<mx;i++){
        bool f=true;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                f=false;
                break;
            }
        }
        if(f){
            ar[k++]=i;
        }
    }
}

int main(){
    FastAF
    d();
    int n;
    cin>>n;
    while(n--){
        int a;cin>>a;
        cout<<ar[--a]<<endl;
    }
return 0;
}

Algo: sqrt with precomputation

Edited by author 11.05.2025 11:58

Edited by author 11.05.2025 12:02

6
0 0 0 0 12 40
ANS: 52

8 7

0 0
16
1 1
2 1
2 0
3 0
3 1
2 2
3 2
4 1
4 3
0 3
0 4
1 4
1 5
-1 5
-1 -1
1 -1
12.00000000000000000000

0 0
5
-1 -1
1 0
0 -1
2 -2
2 4
5.50000000000000000000

0 0
17
-1 -1
5 -1
1 0
1 1
2 2
2 1
3 1
3 3
4 4
4 3
5 3
5 5
0 5
0 6
6 6
6 7
-1 7
24.00000000000000000000

0 0
4
0 -1
1 0
0 1
-1 0
2.00000000000000000000

0 0
4
-1 2
-1 -1
1 0
3 -1
3.6666666666

0 0
3
-1 -1
1 -1
0 1
2.00000000000000000000

0 0
11
0 -1
3 0
2 2
1 1
2 3
0 4
0 3
-1 5
-2 3
0 2
-1 0
10.50000000000000000000

I would appreciate hints(or solution) a lot!

Please e-mail me at addflash@dmc.chat

Why is the sample 50.211, shouldn't the sample be 50.198 because the path (45, 0) -> (50, 1) -> (5, 1) -> (0, 0) is length 50.198?

Is there some constructive approach? I solved it with some tricky bruteforce with optimizations

sum 2e6

find out how to solve the problem for n <= 68. for bigger n just do n = (n - 35) % 34 + 35 and solve the problem for this n.

i think the memory limit should be higher

Отсутствует язык отправки C#

this is a very cool task, it requires a little out-of-the-box thinking, I really liked it

Input:
4 2
1 1
5 3
7 -1
4 7
1 2
3 4

Correct output:
NO

One of the reasons of "WA" might be that your solution incorrectly determines whether two segments intersect or not.

Edited by author 11.04.2020 15:09

Maybe you output multiple answers.

Reason: after output a correct answer,the program should be exit,but you may not do that.


(I'm sorry for my bad English)

Input
2 2
..
..

Output
1


Input
12 12
************
************
************
******..****
******..****
************
************
************
************
************
************
************

Output
1


Input
2 4
....
****

Output
0


Input
4 2
.*
.*
.*
.*

Output
0


Input
2 5
..*..
..*..

Output
0


Input
5 2
..
..
**
..
..

Output
0


Input
12 12
............
............
............
............
............
............
............
............
............
............
............
...........*

Output
0


Input
6 6
......
......
..**..
..**..
......
......

Output
14


Input
6 6
......
......
......
......
......
......

Output
1072


Input
12 12
............
............
............
............
............
............
............
............
............
............
............
............

Output
1076226888605605706

input:
10 3
10
2 4 8 9 9 10 11 18 22 29
output:
8
0 1
0 3
0 3
1 8
1 8
3 9
8 9
9 17
17 21
21 28

input:
10 3
50
70 113 132 135 135 136 140 140 140 144 194 231 242 275 287 337 359 362 381 391 418 432 436 478 530 541 551 553 560 560 567 575 594 631 634 646 649 676 702 728 738 771 824 858 889 907 922 933 976 987
output:
75
60 69
103 112
125 131
125 131
125 134
130 134
130 139
130 139
131 139
134 143
184 193
221 230
232 241
265 274
277 286
327 336
352 358
352 358
371 380
381 390
408 417
426 431
426 431
468 477
520 529
531 540
543 550
543 552
550 552
550 552
565 566
565 566
584 593
624 630
624 630
639 645
639 645
666 675
692 701
718 727
728 737
761 770
814 823
848 857
879 888
897 906
912 921
923 932
966 975
977 986