2014-03-20

■ JOI 2014 春合宿Day1 22:50

4h47mで全完しました。菜園難しすぎる

Bus: 嘘解法力

growing: 気づけばやるだけ

historical: てきとーにsqrt-decompositionするだけ

一応コード

/*
TASK: Historical Research
LANG: C++
NAME: HIR180 JPN03
*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define INF 1000000000
#define eps 1e-10
#define sz (1<<17)
#define sqr 573
ll seg[sz*2];
vectorx;
ll num[100005];
ll ret[100005];
int n,q;
void update(int pos,int val)
{
  ll act=x[pos];
  pos+=sz-1;
  seg[pos]+=act*val;
  while(pos>0)
    {
      pos=(pos-1)/2;
      seg[pos]=max(seg[pos*2+1],seg[pos*2+2]);
    }
  return ;
}
ll get()
{
  return seg[0];
}
struct query
{
  int lb,ub;
  int id;
  query(){}
  query(int lb,int ub,int id):lb(lb),ub(ub),id(id){}
  bool operator < (const query& q) const
  {
    if(lb/sqr != q.lb/sqr) return lb/sqr < q.lb/sqr;
    return ub < q.ub;
  }
};
vectorzip;
int main()
{
  scanf("%d %d",&n,&q);
  for(int i=0;i"%lld",&num[i]);
      x.pb(num[i]);
    }
  sort(x.begin(),x.end());
  x.erase(unique(x.begin(),x.end()),x.end());
  for(int i=0;ifor(int i=0;iint lb,ub; scanf("%d %d",&lb,&ub);
      --lb;
      zip.pb(query(lb,ub,i));
    }
  sort(zip.begin(),zip.end());
  int lb=0,ub=0;
  //[lb,ub)
  for(int i=0;iwhile(zip[i].lb1);
	}
      while(zip[i].lb>lb)
	{
	  update(num[lb++],-1);
	}
      while(zip[i].ub1);
	}
      while(zip[i].ub>ub)
	{
	  update(num[ub++],1);
	}
      ret[zip[i].id]=get();
    }
  for(int i=0;i"%lld\n",ret[i]);
}

ramen: 2人の時に操作を1回にするだけ

明日以降も頑張ります。

ツイートする