結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー reew2nreew2n
提出日時 2015-06-20 13:51:30
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,647 bytes
コンパイル時間 1,487 ms
コンパイル使用メモリ 154,632 KB
実行使用メモリ 15,356 KB
最終ジャッジ日時 2023-09-21 22:03:03
合計ジャッジ時間 3,577 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,544 KB
testcase_01 AC 2 ms
7,588 KB
testcase_02 AC 3 ms
7,520 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
5,444 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 41 ms
5,476 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 140 ms
15,356 KB
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef LL ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<pr,ut> ppr;
typedef vector<ppr> Vppr;
typedef priority_queue<ppr,Vppr,greater<ppr> > PQ;
const int INF=1e+9;

const int SIZE=1<<17;
LL dx[]={0,0,1,-1},dy[]={1,-1,0,0};
LL segval[2][SIZE<<1],segSum[2][SIZE<<1];
LL score[2];
set<ppr> ika;
void queryAdd(int a,int b,int s,int e,int val,int col,int now){
  if(a<=s && e<=b) segval[col][now]+=val;
  else if(e<a||b<s) return;
  else{
    queryAdd(a,b,s,(s+e)/2,val,col,now*2);
    queryAdd(a,b,(s+e+1)/2,e,val,col,now*2+1);
    segSum[col][now]=segSum[col][now*2]+segSum[col][now*2+1]+(segval[col][now*2]+segval[col][now*2+1])*(e-s+1)/2;
  }
}
LL querySum(int a,int b,int s,int e,int col,int now){
  if(a<=s && e<=b) return segSum[col][now]+segval[col][now]*(e-s+1);
  else if(e<a||b<s) return 0;
  else{
    LL alpha=(min(b,e)-max(a,s)+1)*segval[col][now];
    return alpha+querySum(a,b,s,(s+e)/2,col,now*2)+querySum(a,b,(s+e+1)/2,e,col,now*2+1);
  }
}
void add(int a,int b,int val,int col){
  queryAdd(a,b,1,SIZE,val,col,1);
}
int sum(int a,int b,int col){
  return querySum(a,b,1,SIZE,col,1);
}
bool cut(int a,int b,set<ppr>::iterator it){
  int na=(*it).F.S;
  int nb=(*it).F.F;
  int col=(*it).S;
  if(a<=na && nb<=b){  
    add(na,nb,-1,col);  
    ika.erase(it);
    return true;
  }
  else if(b<na||nb<a){
    return false;
  }
  else if(na<a && b<nb){
    ika.insert(ppr(pr(na,a-1),col));
    ika.insert(ppr(pr(b+1,nb),col));
    ika.erase(it);
    add(a,b,-1,col);
    return false;
  }
  else{
    if(a<=nb){
      add(a,nb,-1,col);
      nb=a-1;
    }
    else if(na<=b){
      add(na,b,-1,col);
      na=b+1;
    }
    if(na<=nb) 
      ika.insert(ppr(pr(na,nb),col));
    ika.erase(it);
    return false;
  }

}
int main(){
  LL N,Q,x,l,r;
  cin >> N >> Q;
    ika.insert(ppr(pr(-1,-1),0));
  REP(i,Q){
    scanf("%lld %lld %lld",&x,&l,&r);
    l++;
    r++;
    if(x==0){
      int point[]={sum(l,r,0),sum(l,r,1)};
        REP(i,2)
          if(point[i]>point[i^1]){
            score[i]+=(LL)point[i];
          }
    }
    else{
      add(l,r,1,x-1);
      ika.insert(ppr(pr(r,l),x-1));
      set<ppr>::iterator fit,it=ika.find(ppr(pr(r,l),x-1));
      fit=it;
      if(it!=ika.begin())
      --it;
      if(fit!=ika.end())
      ++fit;
      while(fit!=ika.end() && cut(l,r,fit++));
      while(it!=ika.begin() && cut(l,r,it--));
    }
  }
  REP(i,2)
    cout << (i?" ":"") << score[i]+sum(1,N,i);
  cout << endl;
}
0