제출 #332314

#제출 시각아이디문제언어결과실행 시간메모리
332314errorgorn운세 보기 2 (JOI14_fortune_telling2)C++17
100 / 100
1685 ms159708 KiB
//雪花飄飄北風嘯嘯 //天地一片蒼茫 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; #define ll long long #define ii pair<ll,ll> #define iii pair<ii,ll> #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << " is " << x << endl #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> //change less to less_equal for non distinct pbds, but erase will bug mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); struct node{ int s,e,m; int val=-1; node *l,*r; node (int _s,int _e){ s=_s,e=_e,m=s+e>>1; if (s!=e){ l=new node(s,m); r=new node(m+1,e); } } void update(int i,int j){ val=max(val,j); if (s==e) return; else if (i<=m) l->update(i,j); else r->update(i,j); } int query(int i,int j){ if (s==i && e==j) return val; else if (j<=m) return l->query(i,j); else if (m<i) return r->query(i,j); else return max(l->query(i,m),r->query(m+1,j)); } } *root=new node(0,600005); struct node2{ int s,e,m; int val=0; node2 *l,*r; node2 (int _s,int _e){ s=_s,e=_e,m=s+e>>1; if (s!=e){ l=new node2(s,m); r=new node2(m+1,e); } } void update(int i){ val++; if (s==e) return; else if (i<=m) l->update(i); else r->update(i); } int query(int i,int j){ if (s==i && e==j) return val; else if (j<=m) return l->query(i,j); else if (m<i) return r->query(i,j); else return l->query(i,m)+r->query(m+1,j); } } *root2=new node2(0,600005); int n,q; ii arr[200005]; int brr[200005]; vector<ii> proc; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n>>q; rep(x,0,n) cin>>arr[x].fi>>arr[x].se; rep(x,0,q) cin>>brr[x]; vector<int> uni; rep(x,0,n) uni.push_back(arr[x].fi),uni.push_back(arr[x].se); rep(x,0,q) uni.push_back(brr[x]); sort(all(uni)); uni.erase(unique(all(uni)),uni.end()); map<int,int> id; rep(x,0,sz(uni)) id[uni[x]]=x; rep(x,0,n) arr[x].fi=id[arr[x].fi],arr[x].se=id[arr[x].se]; rep(x,0,q) brr[x]=id[brr[x]]; rep(x,0,q){ root->update(brr[x],x); } rep(x,0,n){ ii temp=arr[x]; if (temp.fi>temp.se) swap(temp.fi,temp.se); int val=-1; if (temp.fi!=temp.se) val=root->query(temp.fi,temp.se-1); proc.push_back(ii(val+1,x)); } sort(all(proc)); int idx=q; ll ans=0; while (!proc.empty()){ while (idx!=proc.back().fi){ idx--; //cout<<"upd: "<<brr[idx]<<endl; root2->update(brr[idx]); } int pos=proc.back().se; bool orient; if (proc.back().fi==0) orient=false; else orient=arr[pos].fi<arr[pos].se; //cout<<idx<<" "<<orient<<endl; //cout<<root2->query(max(arr[pos].fi,arr[pos].se),600005)<<endl; orient^=((root2->query(max(arr[pos].fi,arr[pos].se),600005))%2==1); //cout<<idx<<" "<<orient<<endl; if (!orient) ans+=uni[arr[pos].fi]; else ans+=uni[arr[pos].se]; proc.pop_back(); } cout<<ans<<endl; }

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

fortune_telling2.cpp: In constructor 'node::node(int, int)':
fortune_telling2.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
fortune_telling2.cpp: In constructor 'node2::node2(int, int)':
fortune_telling2.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...