Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不要使用map!!!

Posted by HalfSummer at 2019-03-22 15:25:10 on Problem 2299
不用map600MS,用了map就tle
离散的时候使用原序列进行离散,而不是数据的值
这样开5e5的数组就可以直接查询离散化后的数据了
比如
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<cstdio>
using namespace std;
const int maxn = 500005;
int tnum;
int c[maxn],newnum[maxn];
int Lowbit(int x)
{
    return x&(-x);
}
 
void Add(int n,int val)
{
    while(n<=tnum)
    {
        c[n]+=val;
        n+=Lowbit(n);
    }
}
 
int Query(int n)
{
    int ans = 0;
    while(n>0)
    {
        ans+=c[n];
        n-=Lowbit(n);
    }
    return ans;
}
struct fom
{
    int val;
    int num;
} stu[500005];
 
int cmp(fom a,fom b)
{
    return a.val<b.val;
}
 int cmp2(fom a,fom b)
{
    return a.num<b.num;
}
int main()
{
    int i;
    while(~scanf("%d",&tnum)&&tnum)
    {
        memset(c,0,sizeof(c));
        long long sum=0;
        for(i=1; i<=tnum; i++)
        {
            scanf("%d",&stu[i].val);
            //stu[i].val++;
            stu[i].num=i;
        }
        sort(stu+1,stu+tnum+1,cmp);
        for(i=1; i<=tnum; i++)
        {
            newnum[stu[i].num]=i;
        }
        sort(stu+1,stu+tnum+1,cmp2);
        for(i=tnum; i>=1; i--)
        {
            int nowi=newnum[stu[i].num];
            sum+=Query(nowi-1);
            Add(nowi,1);
        }
        printf("%lld\n",sum);
    }
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator