제출 #1187396

#제출 시각아이디문제언어결과실행 시간메모리
1187396guagua0407Dragon 2 (JOI17_dragon2)C++20
60 / 100
2869 ms7672 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define pll pair<ll,ll> int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } pll operator-(pll a,pll b){ return pll(a.f-b.f,a.s-b.s); } ll cross(pll a,pll b){ return a.f*b.s-a.s*b.f; } int ori(pll a,pll b,pll c){ ll res=cross(b-a,c-a); return (res==0?0:(res>0?1:-1)); } bool comp(pair<pll,int> a,pair<pll,int> b){ pll aa=a.f; pll bb=b.f; #define is_neg(x) (x.s<0 or (x.s==0 and x.f<0)) int A=is_neg(aa); int B=is_neg(bb); if(A!=B) return A<B; return ori(pll(0,0),aa,bb)>0; } const int mxn=1e5+5; const int BB=200; int bit[mxn]; void upd(int pos,int val){ pos++; for(;pos<mxn;pos+=(pos&-pos)){ bit[pos]+=val; } } int query(int pos){ pos++; int ans=0; for(;pos>0;pos-=(pos&-pos)){ ans+=bit[pos]; } return ans; } void update(int l,int r,int val){ upd(l,val); upd(r+1,-val); } int main(){_ int n,m; cin>>n>>m; vector<int> c(n); vector<pll> p(n); vector<int> sz(m); vector<vector<int>> id(m); for(int i=0;i<n;i++){ cin>>p[i].f>>p[i].s>>c[i]; c[i]--; id[c[i]].push_back(i); } for(int i=0;i<m;i++){ sz[i]=(int)id[i].size(); } pll A,B; cin>>A.f>>A.s>>B.f>>B.s; int q; cin>>q; vector<vector<int>> out(n); vector<vector<int>> in(n); vector<int> R1(n),R2(n); vector<int> rev(n); for(int a=0;a<m;a++){ if(sz[a]<=BB) continue; vector<pair<pll,int>> vec; for(int i=0;i<n;i++){ vec.push_back({p[i],i}); } vector<int> ord1,ord2; { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-A,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord1.push_back(tmp[i].s); } } { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-B,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord2.push_back(tmp[i].s); } } int sz=(int)ord1.size(); for(int i=0;i<sz;i++){ rev[ord1[i]]=i; } ord1.insert(ord1.end(),all(ord1)); ord2.insert(ord2.end(),all(ord2)); { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(A,p[ord1[l]],p[ord1[r]])>=0) r++; R1[ord1[l]]=r; } } { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(B,p[ord2[l]],p[ord2[r]])>=0) r++; R2[ord2[l]]=r; } } vector<pair<pair<int,int>,pair<int,int>>> op; auto add=[&](int l1,int r1,int l2,int r2){ if(l1>r1 or l2>r2) return; op.push_back({{l1,1},{l2,r2}}); op.push_back({{r1+1,-1},{l2,r2}}); }; for(int l=0;l<sz;l++){ if(c[ord2[l]]!=a) continue; if(ori(B,p[ord2[l]],A)>=0) add(l,R2[ord2[l]]-1,R1[ord2[l]],rev[ord2[l]]+sz-1); else add(R2[ord2[l]],l+sz-1,rev[ord2[l]],R1[ord2[l]]-1); } sort(all(op)); vector<int> cnt(sz); int pos=0; for(int i=0;i<=2*sz;i++){ while(pos<(int)op.size() and op[pos].f.f==i){ update(op[pos].s.f,op[pos].s.s,op[pos].f.s); pos++; } if(i==2*sz) break; cnt[i%sz]+=query(rev[ord2[i]]%sz)+query(rev[ord2[i]]%sz+sz); } out[a]=vector<int>(m); for(int i=0;i<sz;i++){ if(c[ord2[i]]==a) continue; out[a][c[ord2[i]]]+=cnt[i]; } } for(int a=0;a<m;a++){ if(sz[a]<=BB) continue; vector<pair<pll,int>> vec; for(int i=0;i<n;i++){ vec.push_back({p[i],i}); } vector<int> ord1,ord2; { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-A,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord1.push_back(tmp[i].s); } } { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-B,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord2.push_back(tmp[i].s); } } int sz=(int)ord1.size(); for(int i=0;i<sz;i++){ rev[ord1[i]]=i; } ord1.insert(ord1.end(),all(ord1)); ord2.insert(ord2.end(),all(ord2)); { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(A,p[ord1[l]],p[ord1[r]])>=0) r++; R1[ord1[l]]=r; } } { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(B,p[ord2[l]],p[ord2[r]])>=0) r++; R2[ord2[l]]=r; } } vector<pair<pair<int,int>,pair<int,int>>> op; auto add=[&](int l1,int r1,int l2,int r2){ if(l1>r1 or l2>r2) return; op.push_back({{l1,1},{l2,r2}}); op.push_back({{r1+1,-1},{l2,r2}}); }; for(int l=0;l<sz;l++){ if(c[ord2[l]]!=a) continue; if(ori(B,p[ord2[l]],A)<=0) add(l,R2[ord2[l]]-1,R1[ord2[l]],rev[ord2[l]]+sz-1); else add(R2[ord2[l]],l+sz-1,rev[ord2[l]],R1[ord2[l]]-1); if(ori(B,p[ord2[l]],A)>=0){ int r2=l; while(r2<R2[ord2[l]] and ori(B,p[ord2[r2]],A)>=0) r2++; int r1=R1[ord2[l]]; while(r1<rev[ord2[l]]+sz and ori(A,p[ord1[r1]],B)>=0) r1++; add(r2,R2[ord2[l]]-1,R1[ord2[l]],r1-1); } else{ int r2=R2[ord2[l]]; while(r2<l+sz and ori(B,p[ord2[r2]],A)<=0) r2++; int r1=rev[ord2[l]]; while(r1<R1[ord2[l]] and ori(A,p[ord1[r1]],B)>=0) r1++; add(r2,l+sz-1,rev[ord2[l]],r1); } } sort(all(op)); vector<int> cnt(sz); int pos=0; for(int i=0;i<=2*sz;i++){ while(pos<(int)op.size() and op[pos].f.f==i){ update(op[pos].s.f,op[pos].s.s,op[pos].f.s); pos++; } if(i==2*sz) break; cnt[i%sz]+=query(rev[ord2[i]]%sz)+query(rev[ord2[i]]%sz+sz); } in[a]=vector<int>(m); for(int i=0;i<sz;i++){ if(c[ord2[i]]==a) continue; in[a][c[ord2[i]]]+=cnt[i]; } } auto solve=[&](int a,int b){ vector<pair<pll,int>> vec; for(auto v:id[a]){ vec.push_back({p[v],v}); } for(auto v:id[b]){ vec.push_back({p[v],v}); } vector<int> ord1,ord2; { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-A,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord1.push_back(tmp[i].s); } } { vector<pair<pll,int>> tmp; for(auto v:vec){ tmp.push_back({v.f-B,v.s}); } sort(all(tmp),comp); for(int i=0;i<(int)tmp.size();i++){ ord2.push_back(tmp[i].s); } } int sz=(int)ord1.size(); for(int i=0;i<sz;i++){ rev[ord1[i]]=i; } ord1.insert(ord1.end(),all(ord1)); ord2.insert(ord2.end(),all(ord2)); { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(A,p[ord1[l]],p[ord1[r]])>=0) r++; R1[ord1[l]]=r; } } { int r=0; for(int l=0;l<sz;l++){ while(r<l+sz and ori(B,p[ord2[l]],p[ord2[r]])>=0) r++; R2[ord2[l]]=r; } } vector<pair<pair<int,int>,pair<int,int>>> op; auto add=[&](int l1,int r1,int l2,int r2){ if(l1>r1 or l2>r2) return; op.push_back({{l1,1},{l2,r2}}); op.push_back({{r1+1,-1},{l2,r2}}); }; for(int l=0;l<sz;l++){ if(c[ord2[l]]!=a) continue; if(ori(B,p[ord2[l]],A)>=0) add(l,R2[ord2[l]]-1,R1[ord2[l]],rev[ord2[l]]+sz-1); else add(R2[ord2[l]],l+sz-1,rev[ord2[l]],R1[ord2[l]]-1); } sort(all(op)); vector<int> cnt(sz); int pos=0; for(int i=0;i<=2*sz;i++){ while(pos<(int)op.size() and op[pos].f.f==i){ update(op[pos].s.f,op[pos].s.s,op[pos].f.s); pos++; } if(i==2*sz) break; cnt[i%sz]+=query(rev[ord2[i]]%sz)+query(rev[ord2[i]]%sz+sz); } int ans=0; for(int i=0;i<sz;i++){ if(c[ord2[i]]!=b) continue; ans+=cnt[i]; } return ans; }; for(int i=0;i<q;i++){ int a,b; cin>>a>>b; a--; b--; if(sz[a]<=BB and sz[b]<=BB){ cout<<solve(a,b)<<'\n'; } else if(sz[a]>BB){ cout<<out[a][b]<<'\n'; } else{ cout<<in[a][b]<<'\n'; } } return 0; } //maybe its multiset not set //yeeorz //diaoborz

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

dragon2.cpp: In function 'void setIO(std::string)':
dragon2.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...