At first I converted all the things to indices. for example
if n = 5
2 4 5 2 4
and
m = 1
4 2 2    -> 1 - 2, and 4 - 5 <= these are all index.
Then I got only some pair of index. From these I calculate the 11011. THere may be index intersections.
That is my code. I think its time and algo is ok. But I got wa3



import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Timus1827 {
    public static void main(String [] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int [] a = new int[n];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for(int i = 0; i < n; i++){
            a[n - i - 1] = input.nextInt();
            if(map.get(a[n - i - 1]) == null){
                map.put(a[n - i - 1], new ArrayList<Integer>());
            }
            map.get(a[n - i - 1]).add(n - i - 1);
        }

        int m = input.nextInt();
        int[] h = new int[n];
        boolean[] dontuse = new boolean[n];
        Arrays.fill(dontuse, false);
        Arrays.fill(h, -1);
        for(int i = 0; i < m; i++){
            int x = input.nextInt();
            int y = input.nextInt();
            int d = input.nextInt() - 1;
            if(map.containsKey(x))
                for(int j : map.get(x)){
                    if(j + d < n && a[j + d] == y){
                        h[j] = Math.max(h[j], j + d);
                        dontuse[j] = true;

                    }
                }
        }

        int k = -1;
        for(int i = 0; i < n; i++){
            if(dontuse[i]) {
                k = i;
                break;
            }
        }


        int j = k;
        for(int i = k + 1; i < n; i++){
            if(dontuse[i]){
                if(h[j] + 1 >= i){
                    h[j] = h[i];
                    dontuse[i] = false;
                }
                else{
                    j = i;
                }
            }
        }

        int[] ans = new int[n];
        Arrays.fill(ans, 0);
        for(int i = 0; i <n; i++){
            if(dontuse[i]){
                for(j = i; j <= h[i]; j++){

                    ans[j] = 1;

                }

            }
        }
        for (int i = 0; i < n; i++)
            System.out.print(ans[i]);
    }
}

my algo should be n*50*order of hash
probably large input is causing problem

i can use fread and fwrite but don't know how to do it in online judge submission.
please provide me with some code segment that utilize fread and fwrite.
better be some eg problem as 1000. a+b problem

thanks in advance.

Sent on timus_support a couple of good tests, which my program that works 0.25 sec on timus, passes in about 1 minute on my PC

What's the answer for these tests?

#1
8
4 3 2 1 4 3 2 1
2
1 2 2
3 4 2

#2
8
4 3 2 1 4 3 2 1
2
3 4 2
1 2 2

thanks.

tle at test 22...

Powers of all the numbers in statement was disappeared. Restore them, please.
My browser is Opera 11.01.

what answer for
3
6 5 4
1
1 5 5

I think, it is
011
it's right?

edited: no, answer is 000

Edited by author 20.03.2011 09:53

TL with scanf / putchar
AC with fread / fwrite (0.281 s)
Don't like problems with such hacks :\

Sorry, my bad. Anyway, can natives be at war more than n days ago?

For example, what's the answer for this test:

1
1
1
2 1 2

?

Edited by author 19.03.2011 16:41

Can various fightings begin in one day?