제출 #825568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825568		kebine	Addk (eJOI21_addk)	C++17	92 / 100	365 ms	1048576 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
  int line, diag;
  node(int line=0, int diag=0) : line(line), diag(diag) {}
};
node combine(node L, node R) {
  return node(L.line+R.line, L.diag+R.diag);
}
int n, k;
vector<int> a;
vector<node> tr;
void build(int pos=0, int l=0, int r=n-1) {
  if(l==r) {tr[pos]=node(a[l], l*a[r]); return;}
  int mid=l+r>>1;
  build(2*pos+1, l, mid);
  build(2*pos+2, mid+1, r);
  tr[pos]=combine(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
  if(ll>rr || ll>r || l>rr) return node();
  if(ll==l && rr==r) return tr[pos];
  int mid=l+r>>1;
  return combine(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> k;
  a.resize(n); tr.resize(n << 2);
  for(int &p : a) cin >> p;
  build();
  int q; cin >> q;
  while(q--) {
    int type, l;; cin >> type >> l;
    if(type==1) continue;
    int r, m, ans; cin >> r >> m;
    --l; --r;
    if(r-m+1<=l+m-1) {
      ans=(r-l-m+2)*get(r-m+1, l+m-1).line;
      ans+=get(l, r-m).diag-(l-1)*get(l, r-m).line;
      ans-=get(l+m, r).diag-(r+1)*get(l+m, r).line;
    } else {
      ans=m*get(l+m-1, r-m+1).line;
      ans+=get(l, l+m-2).diag-(l-1)*get(l, l+m-2).line;
      ans-=get(r-m+2, r).diag-(r+1)*get(r-m+2, r).line;
    }
    cout << ans << '\n';
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int mid=l+r>>1;
      |           ~^~
Main.cpp: In function 'node get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=l+r>>1;
      |           ~^~

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 0 / 8