제출 #770479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
770479		Dan4Life	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	11 ms	976 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi = vector<int>;
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)1e6+1;
vector<pair<int,int>> v;
int seg[mxN*2], lzy[mxN*2];
 
void prop(int p, int l, int r){
    if(l==r or !lzy[p]) return;
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    lzy[p+1]+=lzy[p], lzy[rp]+=lzy[p];
    seg[p+1]+=lzy[p], seg[rp]+=lzy[p], lzy[p]=0;
}
 
void upd(int i, int j, int v, int p=0, int l=0, int r=mxN){
    if(i>r or j<l or i>j) return; prop(p,l,r);
    if(i<=l and r<=j){ seg[p]+=v,lzy[p]+=v; return; }
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=mid) upd(i,j,v,p+1,l,mid);
    if(j>mid) upd(i,j,v,rp,mid+1,r);
    seg[p] = max(seg[p+1],seg[rp]);
}
 
void add(int i, int x){
    int ind = lower_bound(all(v),make_pair(x,i))-begin(v);
    upd(ind,ind+1,(i+1)*x);
    ind = lower_bound(all(v),make_pair(x,-1))-begin(v);
    upd(ind,mxN,x);
}
 
vi countScans(vi a, vi x, vi y){
    int q = sz(x), n = sz(a); vi ans;
    for(int i = 0; i < n; i++) v.pb({a[i],i});
    for(int i = 0; i < q; i++) v.pb({y[i],x[i]});
    sort(all(v)); v.erase(unique(all(v)),end(v));
    for(int i = 0; i < n; i++) add(i,1);
    for(int i = 0; i < q; i++)
        add(x[i],-1),a[x[i]]=y[i],add(x[i],1),ans.pb(seg[0]);
	return ans;
}

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

bubblesort2.cpp: In function 'void upd(int, int, int, int, int, int)':
bubblesort2.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(i>r or j<l or i>j) return; prop(p,l,r);
      |     ^~
bubblesort2.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(i>r or j<l or i>j) return; prop(p,l,r);
      |                                   ^~~~
bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for(int i = 0; i < q; i++)
      |     ^~~
bubblesort2.cpp:43:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |  return ans;
      |  ^~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40