Здравствуйте! Может кто подсказать, почему код не работает? Специально для задачи изучил дерево Фенвика и на питоне всё равно не заработало (на 9 задаче по времени не прошло)

******************************************************
n=int(input())
mas=[0]*n
xp=[0]*32002
for i in range(n):
    lis=list(map(int,input().split()))                #Принимается на ввод пара координат
    if (lis[0]-1)%4==0:
        if lis[0]!=1:
            mas[xp[lis[0]]+xp[lis[0]-2]]+=1

            for j in range(lis[0]+2,32002,4):
                xp[j]+=1
        else:
            mas[xp[lis[0]]]+=1
            for j in range(lis[0]+2,32002,4):
                xp[j]+=1

    else:
        if (lis[0]+1)%4==0:
            mas[xp[lis[0]]]+=1

            for j in range(lis[0]+4,32002,4):
                xp[j]+=1
        else:
            if lis[0]%2==0:
                if lis[0]!=0:
                    if lis[0]%4==0:
                        mas[xp[lis[0]]+xp[lis[0]-1]]+=1
                        xp[lis[0]+1]+=1
                        for j in range(lis[0]+3,32002,4):
                            xp[j]+=1
                    else:
                        mas[xp[lis[0]+1]-(xp[lis[0]+1]-xp[lis[0]-1]-xp[lis[0]-3])]+=1
                        for j in range(lis[0]+1,32002,4):
                            xp[j]+=1
                else:
                    mas[xp[lis[0]]]+=1
                    xp[lis[0]+1]+=1
                    for j in range(lis[0]+3,32002,4):
                        xp[j]+=1
    xp[lis[0]]+=1
for i in mas:
    print(i)
**************************************

Can someone tell me how I can solve thi problem using ordered set?

I've been stuck in this problem for a very long time, but today I got the idea of Binary Indexed Tree from wikipedia and finally solved this problem :)
Binary Indexed Tree,or BIT, can be viewed as a simplified version of Segment Tree,easier to code and less function to perform. But It's enough to solve this problem

#include<iostream>
#include<cstdio>
using namespace std;

const int Max = 32005;

int n;
int c[Max] = {0};
int level[Max] = {0};

int lowbit(int x)
{
    return x&(-x);
}

int sum(int i)
{
    int s = 0;
    while(i > 0)
    {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

void update(int pos,int val)
{
    while(pos <= Max)
    {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[ sum(x) ] ++;
        update(x,1);
    }

    for(int i = 0; i < n; i ++)    printf("%d\n",level[i]);
}

If you are a C++ user, learn about ordered_set in Policy Based Data Structures.

Do you know this content, please?

Why has array
t = new Int16[32000, 32000];
always got a "Runtime Error"? Is "Memory exception in that case?
I dont understand, that this size is incorrect!
I use fenwick tree of two axis dimensions.

Edited by author 15.11.2018 21:11

Edited by author 15.11.2018 21:11

I have an O(n*log(n)) algorithm, which works successfull on all test
cases at my Celeron 300. The time of working is incredible low (I
used test with 15000 stars), but timus gives me Time limit exceeded.
If anyone here has an idea where is the matter, I am ready to share
my program with him.

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct f{
    int a, b;
}b[64006];
bool shart(f a, f b){
    return a.b > b.b;
}
int x, y, q, n, mx;
int main()
{
    cin >> n;
    q = 1;
    for (int i = 0; i < n; i ++){
        cin >> x >> y;
        if(b[x + y].a){
           b[x + y].a ++;
        }
        else{
           b[x + y].a ++;
           b[x + y].b = q;
           q ++;
        }

    }
    sort(b, b + 2 * 32002, shart);
    for (int i = q - 2; i >= 0; i --)
            cout << b[i].a << endl;
    for (int i = q; i <= n; i ++)
        cout << 0 << endl;
}

 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.

Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.

I got TL although i'm using the binary tree , and when I looked for a solution on the net i found the same of mine but in another words
here is my code:

#include <cstdio>
#include <cstring>

using namespace std;
#define max 32002
int a[max];
void update(int i,int n,int v)
{
    while(i<=n)
    {
        a[i]+=v;
        i+=i&(-i);
    }

}
int read(int i)
{
    int v=0;
    while(i>0)
    {
        v+=a[i];
        i-=i&(-i);
    }
    return v;

}

int main()
{
    int n;
    scanf("%d",&n);

    int b[15010];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);


        b[read(x)]++;
        update(x,32002,1);
    }
    for(int i=0;i<n;i++)
        printf("%d \n",b[i]);
    return 0;
}

so please help me cause i'm about to lose my mind!!!

Ordering of start can be exploited to find solution.

Edited by author 22.03.2015 03:35

why i always got wrong 3 ?

Double post, please remove this one.

Edited by author 06.08.2013 17:09

Edited by author 06.08.2013 17:14

Can you give me some "extra" test or smth like that... My prog passed all my tests but i get wa#3...

Thnx!

why my program give wrong answer?

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <sstream>
using namespace std;
struct RPair
{
    int x;
    int y;
};
int main()
{
    int N;
    while(cin>>N)
    {
       int p1,p2;
       RPair P;
       vector<int> x_hold;
       vector<int> y_hold;
       vector<RPair> P_hold;
          string  stringx_hold;
           string stringy_hold;
       vector<int> level;
       level.resize(N);
       ostringstream convert;
       string result;
        for(int i=0;i<N;i++)
        {
            cin>>p1>>p2;
              x_hold.push_back(p1);
              y_hold.push_back(p2);
              P.x=p1;P.y=p2;
              P_hold.push_back(P);
              convert<<p1;
              result=convert.str();
              stringx_hold+=result[result.size()-1];
             convert<<p2;
              result=convert.str();
              stringy_hold+=result[result.size()-1];
        }
    sort(x_hold.begin(),x_hold.end());
    sort(y_hold.begin(),y_hold.end());
    sort(stringx_hold.begin(),stringx_hold.end());
    sort(stringy_hold.begin(),stringy_hold.end());
    for(int i=0;i<P_hold.size();i++)
    {
        RPair temp;
        for(int j=0;j<P_hold.size();j++)
        {
            if(P_hold[i].x<P_hold[j].x)
            {
               temp=P_hold[i];
               P_hold[i]=P_hold[j];
               P_hold[j]=temp;
            }
            if(P_hold[i].x==P_hold[j].x&&P_hold[i].y<P_hold[j].y)
            {
               temp=P_hold[i];
               P_hold[i]=P_hold[j];
               P_hold[j]=temp;
            }
        }
    }
    size_t found;
    int t=0;
    for(int i=0;i<x_hold.size();i++)
    {
        t=i;
        if(i!=x_hold.size()-1)
        {
            while(P_hold[t].x==P_hold[t+1].x&&P_hold[t].y==P_hold[t+1].y)
            {
                t++;
              if(t==x_hold.size()-1)
                  break;
            }
        }
        if(i==t)
        {
        convert<<P_hold[t].y;
        result=convert.str();
        found=stringy_hold.find(result[result.size()-1]);
        level[min((int)found,t)]++;
        //stringy_hold.insert((int)found,"n");
        stringy_hold.replace((int)found,1,"n");
        }
        else
        {
     int hold=  level[t]++;
        //stringy_hold.insert((int)found,"n");
        stringy_hold.replace(t,1,"n");
        for(int j=i;j<t;j++)
        {
            level[t]++;
             stringy_hold.replace(j,1,"n");
        }
        }
        i=t;
    }
     for(int i=0;i<level.size();i++)
         cout<<level[i]<<"\n";
     }
}

MY ALGO TIME CONSUMED IS(250+128)*N unit

my method is:

divide distance between [0,32000] to 128 sector
each sector is total of stars that occured in that portion
hence for each x, level x calcute of bottom formula
level = sector[x/250]+ Xpivot[i] that i=int(x/250)*250 to x
in last update value of all sector that indexs greater than this sector index;