제출 #1099259

#제출 시각아이디문제언어결과실행 시간메모리
1099259modwweEmployment (JOI16_employment)C++17
100 / 100
156 ms12572 KiB
#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC optimize("conserve-stack") #include<bits/stdc++.h> //#define int long long #define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; #define getchar_unlocked getchar inline int scan() { char c = getchar_unlocked(); int x = 0; while (c < '0' || c > '9') { c = getchar_unlocked(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar_unlocked(); } return x; } void phongbeo(); const int inf = 1e18; const int mod2 = 1e9 + 7; const int mod1 = 998244353; struct icd { long double a; int b; }; struct ib { int a; int b; }; struct ic { int a, b, c; }; struct id { int a, b, c, d; }; struct ie { int a, b, c, d, e; }; int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, l, r, mid, l2, r2, center; int i, s10, s12,k1,k2,k3,s11,t,lim,w; int kk; int el = 19; main() { if(fopen(task".inp","r")) { fin(task); fou(task); } NHP /// cin>>s1; ///modwwe phongbeo(); // checktime } int a[200001]; int b[200001]; struct bit { int bit[500001]; void upd(int x,int y) { for(x; x<=k; x+=x&-x) bit[x]+=y; } int get(int x) { int s=0; for(x; x; x-=x&-x) s+=bit[x]; return s; } } fen; struct IT { int t[800001]; void build(int node,int l,int r) { if(l==r) { t[node]=a[l]; return; } int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); t[node]=max(t[node<<1],t[node<<1|1]); } void upd(int node,int l,int r,int l1) { if(l==r) { t[node]=a[l]; return; } int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1); else upd(node<<1|1,mid+1,r,l1); t[node]=max(t[node<<1],t[node<<1|1]); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node]; int mid=l+r>>1; return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1)); } } st; void solve_left() { for(int i=2; i<=n; i++) { if(a[i-1]<a[i]) { fen.upd(a[i-1]+1,1), fen.upd(a[i]+1,-1); } } } void del2(int x) { if(x==n+1)return; if(x==1) return; if(a[x-1]>=a[x])return; fen.upd(a[x-1]+1,-1); fen.upd(a[x]+1,1); } void del(int x) { del2(x+1); del2(x); } void add2(int x) { if(x==n+1) return; if(x==1) return; if(a[x-1]>=a[x])return; fen.upd(a[x-1]+1,1); fen.upd(a[x]+1,-1); } void add(int x) { add2(x); add2(x+1); } void upd(int x,int y) { del(x); a[x]=y; st.upd(1,1,n,x); add(x); } vector<int> v; vector<ic> v2; void phongbeo() { cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i],v.pb(a[i]); for(int i=1; i<=m; i++) { cin>>l; if(l==2) { cin>>l>>r; v.pb(r); v2.pb({2,l,r}); } else { cin>>l; v2.pb({1,l,0}); } } sort(v.begin(),v.end()); for(int i=1; i<=n; i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; for(int i=1; i<=n; i++) b[i]=max(b[i-1],a[i]); k=v.size(); st.build(1,1,n); solve_left(); for(int i=1; i<=m; i++) { if(v2[i-1].a==2) { l=v2[i-1].b; r=v2[i-1].c; r=lower_bound(v.begin(),v.end(),r)-v.begin()+1; upd(l,r); continue; } r=v2[i-1].b; /// cout<<st.t[1],down if(r>v[st.t[1]-1])cout<<0,down else { r=lower_bound(v.begin(),v.end(),r)-v.begin()+1; s2=fen.get(r)+1; if(a[1]<r) s2--; cout<<s2,down } } }

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

employment.cpp:37:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   37 | const int inf = 1e18;
      |                 ^~~~
employment.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~
employment.cpp: In member function 'void bit::upd(int, int)':
employment.cpp:90:13: warning: statement has no effect [-Wunused-value]
   90 |         for(x; x<=k; x+=x&-x)
      |             ^
employment.cpp: In member function 'int bit::get(int)':
employment.cpp:96:13: warning: statement has no effect [-Wunused-value]
   96 |         for(x; x; x-=x&-x)
      |             ^
employment.cpp: In member function 'void IT::build(int, int, int)':
employment.cpp:111:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid=l+r>>1;
      |                 ~^~
employment.cpp: In member function 'void IT::upd(int, int, int, int)':
employment.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid=l+r>>1;
      |                 ~^~
employment.cpp: In member function 'int IT::get(int, int, int, int, int)':
employment.cpp:132:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid=l+r>>1;
      |                 ~^~
employment.cpp: In function 'int main()':
employment.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
employment.cpp:73:9: note: in expansion of macro 'fin'
   73 |         fin(task);
      |         ^~~
employment.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
employment.cpp:74:9: note: in expansion of macro 'fou'
   74 |         fou(task);
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...