제출 #348433

#제출 시각아이디문제언어결과실행 시간메모리
348433dualityRuka (COI15_ruka)C++11
100 / 100
384 ms12140 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int diff(int a,int b) { return (a > 0) != (b > 0); } int x[100000],y[100000]; int a[100001],b[100001]; struct node { node *l,*r; int sum; }; node *tree1,*tree2; int update(int s,int e,int ai,node *n,int num) { if (s == e) { n->sum += num; return 0; } int mid = (s+e) / 2; if (n->l == NULL) n->l = new node,n->l->l = n->l->r = NULL,n->l->sum = 0; if (n->r == NULL) n->r = new node,n->r->l = n->r->r = NULL,n->r->sum = 0; if (ai <= mid) update(s,mid,ai,n->l,num); else update(mid+1,e,ai,n->r,num); n->sum = n->l->sum+n->r->sum; return 0; } int query(int s,int e,int qs,int qe,node *n) { if ((s > qe) || (e < qs)) return 0; else if ((s >= qs) && (e <= qe)) return n->sum; int mid = (s+e) / 2; int ans = 0; if (n->l != NULL) ans += query(s,mid,qs,qe,n->l); if (n->r != NULL) ans += query(mid+1,e,qs,qe,n->r); return ans; } int update(int i,int num,int t) { if (t == 0) update(0,1.1e8,i+5.05e7,tree1,num); else update(0,1.1e8,i+5.05e7,tree2,num); return 0; } int query(int i,int t) { if (t == 0) return query(0,1.1e8,0,i+5.05e7,tree1); else return query(0,1.1e8,0,i+5.05e7,tree2); } int main() { int i; int N,M; char c; int nx,ny; int u = 0,ans = 0,adda = 0,addb = 0; scanf("%d",&N); a[0] = b[0] = 1; for (i = 0; i < N; i++) scanf("%d %d",&x[i],&y[i]),a[i+1] = a[i]+x[i],b[i+1] = b[i]+y[i]; ans += diff(a[0],a[1])+diff(b[0],b[1]); tree1 = new node,tree2 = new node; tree1->l = tree1->r = NULL,tree1->sum = 0; tree2->l = tree2->r = NULL,tree2->sum = 0; for (i = 1; i < N; i++) { update(min(a[i],a[i+1]),1,0),update(max(a[i],a[i+1])+1,-1,0); update(min(b[i],b[i+1]),1,1),update(max(b[i],b[i+1])+1,-1,1); } scanf("%d",&M); for (i = 0; i < M; i++) { scanf(" %c",&c); if (c == 'B') { if (u == 0) continue; ans -= diff(a[u],a[u+1]+adda)+diff(b[u],b[u+1]+addb); a[u] -= adda,b[u] -= addb; update(min(a[u],a[u+1]),1,0),update(max(a[u],a[u+1])+1,-1,0); update(min(b[u],b[u+1]),1,1),update(max(b[u],b[u+1])+1,-1,1); u--; } else if (c == 'F') { if (u == N-1) continue; u++; update(min(a[u],a[u+1]),-1,0),update(max(a[u],a[u+1])+1,1,0); update(min(b[u],b[u+1]),-1,1),update(max(b[u],b[u+1])+1,1,1); a[u] += adda,b[u] += addb; ans += diff(a[u],a[u+1]+adda)+diff(b[u],b[u+1]+addb); } else if (c == 'C') { scanf("%d %d",&nx,&ny); ans -= diff(a[u],a[u+1]+adda)+diff(b[u],b[u+1]+addb); adda += nx-x[u],addb += ny-y[u]; ans += diff(a[u],a[u+1]+adda)+diff(b[u],b[u+1]+addb); x[u] = nx,y[u] = ny; } else printf("%d\n",ans+query(-adda,0)+query(-addb,1)); } return 0; }

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

ruka.cpp: In function 'int main()':
ruka.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
ruka.cpp:109:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |     for (i = 0; i < N; i++) scanf("%d %d",&x[i],&y[i]),a[i+1] = a[i]+x[i],b[i+1] = b[i]+y[i];
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
ruka.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |     scanf("%d",&M);
      |     ~~~~~^~~~~~~~~
ruka.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
ruka.cpp:138:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |             scanf("%d %d",&nx,&ny);
      |             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...