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

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

#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;
}

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

Ordering of start can be exploited to find solution.

Edited by author 22.03.2015 03:35

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!!!

 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.

Double post, please remove this one.

Edited by author 06.08.2013 17:09

Edited by author 06.08.2013 17:14

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";
     }
}

Hi, This is my code and it gives Access Violation on test case #1 . Please Help. Its running fine on my system.

#include<stdio.h>
#include<stdlib.h>
struct Tree {
    struct Tree *left;
    struct Tree *right;
    int x;
    int lsize;
};
int insert(struct Tree *root, int x){
    struct Tree *temp =(struct Tree *) malloc(sizeof(struct Tree));
    temp->x = x;
    temp->left = NULL;
    temp->right = NULL;
    temp->lsize=0;
    struct Tree *temp2 = root;
    int flag = 0;
    int count = 0;
    struct Tree *prev = NULL;
    while(temp2!=NULL){
        if(temp2->x>temp->x){
            flag = 0;
            prev = temp2;
            temp2->lsize++;
            temp2 = temp2->left;
        }
        else{
            flag = 1;
            prev = temp2;
            count = count + 1 + prev->lsize;
            temp2 = temp2->right;
        }
    }
    if (flag==0) prev->left = temp;
    else prev->right = temp;
    return count;
}

int main(){
    int n;
    scanf("%d", &n);
    int i = 1;
    int x,y;
    scanf("%d %d", &x, &y);
    struct Tree *root = (struct Tree *) malloc(sizeof(struct Tree));
    root->x = x;
    root->left = NULL;
    root->right = NULL;
    int *ans =(int *)  malloc(n*sizeof(int));
    int j = 0;
    while(j<n){
        ans[j]=0;
        j++;
    }
    ans[0]++;
    while (i<n) {
        scanf("%d %d", &x,&y);
        int k = insert(root,x);
        ans[k]++;
        i++;
    }
    i = 0;
    while(i<n){
        printf("%d \n", ans[i]);
        i++;
    }
    return 0;
}

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]);
}

var
        s:array[1..32000]of longint;
        ans:array[0..15000]of longint;
        n,i,x,y,t,k:longint;
begin
        readln(n);
        for i:=1 to n do
         begin
                readln(x,y);
                t:=0; inc(x); k:=x;
                while k>0 do
                 begin
                        t:=t+s[k];
                        k:=k-k and (k xor (k-1));
                 end;
                ans[t]:=ans[t]+1;
                k:=x;
                while k<=32000 do
                 begin
                        s[k]:=s[k]+1;
                        k:=k+k and (k xor (k-1));
                 end;
         end;
        for i:=0 to n-1 do writeln(ans[i]);
end.

Why WA? Just tree node, who have data? Please give me one.
var
n,i,j,k,count:integer;
c,x,y,sum:array[1..15000]of integer;
function lowbit(x:integer):integer;
begin
exit(x and (-x));
end;
procedure increase(k:integer);
var
s:integer;
begin
s:=k;
while s<n do begin
inc(c[s]);
s:=s+lowbit(s);
end;
end;
function getsum(k:integer):integer;
var
s,t:integer;
begin
t:=0;
s:=k;
while s>0 do begin
t:=t+c[s];
s:=s-lowbit(s);
end;
exit(t);
end;
begin
fillchar(c,sizeof(c),0);
readln(n);
for i:=1 to n do begin
readln(x[i],y[i]);
count:=1;
if i=1 then begin increase(1); continue; end;
for j:=i-1 downto 1 do
if x[j]<=x[i] then inc(count);
increase(count);
end;
for i:=1 to n do sum[i]:=getsum(i);
writeln(sum[1]);
for i:=2 to n do
writeln(sum[i]-sum[i-1]);
end.

I'm using BIT

this is my c++ solution

#include <stdio.h>

#define mxn 15005
#define mxm 32005

int l[mxn];
int b[mxm];
int n;

int get(int x)
{
    int s = 0;
    while(x > 0)
    {
            s += b[x];
            x -= (x & -x);
    }
    return s;
}

void add(int x)
{
    while(x < mxm)
    {
        b[x]++;
        x += (x & -x);
    }
}

int main()
{
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
                int a,b;
                a++;
                scanf("%d%d",&a,&b);
                l[get(a)]++;
                add(a);
        }

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

int main()
{
    int N = 0;
    scanf("%d",&N);
    rangs = new int[N];
    Star *stars = new Star[N];

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &stars[i].x, &stars[i].y);
    }

    qsort(stars, N, sizeof(Star), StarCompare);

    AVLTreeNode *root = new AVLTreeNode();

    for(int i = 0; i < N; i++) {
        rangs[i] = 0;
    }

    for(int i = 0; i < N; i++) {
        AVLTreeNode::Insert(root, stars[i].y, 0);
    }

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

    return 0;
}

Edited by author 05.02.2011 00:23