結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー reew2n
提出日時 2015-06-20 13:51:30
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,647 bytes
コンパイル時間 1,541 ms
コンパイル使用メモリ 168,328 KB
実行使用メモリ 14,592 KB
最終ジャッジ日時 2024-07-07 15:12:36
合計ジャッジ時間 3,451 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:85:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |     scanf("%lld %lld %lld",&x,&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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