답안 #27289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
27289	2017-07-12T07:11:10 Z	구사과(#1145)	Dragon 2 (JOI17_dragon2)	C++	컴파일 오류	0 ms	0 KB

dragon2

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct pnt{
	int x, y, c;
	int r1, r2;
}a[30005], s, e;

lint ccw(pnt a, pnt b, pnt c){
	return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}

int n, m;
int stx[30005], sty[30005], edx[30005], edy[30005];

void label1(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(s, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r1 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = i;
		edx[i] = p;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(s, a[i], a[p]) > 0) p++;
		stx[i] = p;
		edx[i] = i;
	}
}

void label2(){
	sort(a, a+n, [&](const pnt &p, const pnt &q){
		bool bh1 = ccw(s, e, p) > 0;
		bool bh2 = ccw(s, e, q) > 0;
		if(bh1 != bh2) return bh1 > bh2;
		return ccw(e, p, q) > 0;
	});
	int dv = 0;
	for(int i=0; i<n; i++){
		a[i].r2 = i;
		if(ccw(s, e, a[i]) > 0) dv = i+1;
	}
	int p = 0;
	for(int i=dv; i<n; i++){
		while(p < dv && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = p;
		edy[i] = i;
	}
	p = dv;
	for(int i=0; i<dv; i++){
		while(p < n && ccw(e, a[i], a[p]) > 0) p++;
		sty[i] = i;
		edy[i] = p;
	}
}

vector<pi> grp[30005];
map<pi, int> mp;
int refer[100005], ans[100005];

struct sweep1{
	int pos, s, e, dx, idx;
	bool operator<(const sweep1 &c)const{
		return pos < c.pos;
	}
};

vector<sweep1> s1[30005];

void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
	if(sx > ex || sy > ey) return;
	s1[gnum].push_back({sx - 1, sy, ey, -1, idx});
	s1[gnum].push_back({ex, sy, ey, 1, idx});
}

void add_sweep2(int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
	}
}

void add_sweep3(int x, int y, int gnum, int idx){
	for(auto &i : grp[gnum]){
		if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
	}
}

struct bit{
	int tree[30005];
	void add(int x, int v){
		x += 2;
		while(x <= n+2){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

void proc_sweep(int gnum){
	sort(s1[gnum].begin(), s1[gnum].end());
	sort(grp[gnum].begin(), grp[gnum].end());
	int p = 0;
	for(auto &i : s1[gnum]){
		while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
			bit.add(grp[gnum][p++].second, 1);
		}
		ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
	}
	while(p > 0){
		bit.add(grp[gnum][--p].second, -1);
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
	}
	scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
	label1();
	label2();
	for(int i=0; i<n; i++){
		grp[a[i].c].push_back(pi(a[i].r1, a[i].r2));
	}
	int q;
	scanf("%d",&q);
	for(int i=1; i<=q; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		if(mp.find(pi(x, y)) != mp.end()){
			refer[i] = mp[pi(x, y)];
			continue;
		}
		if(grp[x].size() < grp[y].size()){
			for(auto &j : grp[x]){
				add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
				add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
			}
		}
		else{
			for(auto &j : grp[y]){
				add_sweep2(j.second, x, i);
				add_sweep3(j.first, j.second, x, i);
			}
		}
		mp[pi(x, y)] = i;
	}
	for(int i=1; i<=m; i++) proc_sweep(i);
	for(int i=1; i<=q; i++){
		if(refer[i]) printf("%d\n", ans[refer[i]]);
		else printf("%d\n", ans[i]);
	}
}

Compilation message

dragon2.cpp: In function 'void label1()':
dragon2.cpp:25:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
dragon2.cpp:25:3: error: no matching function for call to 'sort(pnt [30005], pnt*, label1()::<lambda(const pnt&, const pnt&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
dragon2.cpp:25:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
dragon2.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = pnt*; _Compare = label1()::<lambda(const pnt&, const pnt&)>]':
dragon2.cpp:25:3:   required from here
dragon2.cpp:25:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'label1()::<lambda(const pnt&, const pnt&)>'
  });
   ^
dragon2.cpp:25:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
dragon2.cpp: In function 'void label2()':
dragon2.cpp:51:2: warning: lambda expressions only available with -std=c++11 or -std=gnu++11
  });
  ^
dragon2.cpp:51:3: error: no matching function for call to 'sort(pnt [30005], pnt*, label2()::<lambda(const pnt&, const pnt&)>)'
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4689:5: note: candidate: template<class _RAIter> void std::sort(_RAIter, _RAIter)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     ^
/usr/include/c++/5/bits/stl_algo.h:4689:5: note:   template argument deduction/substitution failed:
dragon2.cpp:51:3: note:   candidate expects 2 arguments, 3 provided
  });
   ^
In file included from /usr/include/c++/5/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:64,
                 from dragon2.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note: candidate: template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   template argument deduction/substitution failed:
dragon2.cpp: In substitution of 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = pnt*; _Compare = label2()::<lambda(const pnt&, const pnt&)>]':
dragon2.cpp:51:3:   required from here
dragon2.cpp:51:3: error: template argument for 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)' uses local type 'label2()::<lambda(const pnt&, const pnt&)>'
  });
   ^
dragon2.cpp:51:3: error:   trying to instantiate 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
dragon2.cpp: In function 'void add_sweep(int, int, int, int, int, int)':
dragon2.cpp:86:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  s1[gnum].push_back({sx - 1, sy, ey, -1, idx});
                     ^
dragon2.cpp:86:46: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  s1[gnum].push_back({sx - 1, sy, ey, -1, idx});
                                              ^
dragon2.cpp:87:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  s1[gnum].push_back({ex, sy, ey, 1, idx});
                     ^
dragon2.cpp:87:41: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  s1[gnum].push_back({ex, sy, ey, 1, idx});
                                         ^
dragon2.cpp: In function 'void add_sweep2(int, int, int)':
dragon2.cpp:91:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : grp[gnum]){
      ^
dragon2.cpp:91:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : grp[gnum]){
            ^
dragon2.cpp:91:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : grp[gnum]){
                ^
dragon2.cpp:92:12: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
            ^
dragon2.cpp:92:38: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
                                      ^
dragon2.cpp: In function 'void add_sweep3(int, int, int, int)':
dragon2.cpp:97:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : grp[gnum]){
      ^
dragon2.cpp:97:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : grp[gnum]){
            ^
dragon2.cpp:97:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : grp[gnum]){
                ^
dragon2.cpp:98:12: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
            ^
dragon2.cpp:98:37: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                     ^
dragon2.cpp:98:53: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                                     ^
dragon2.cpp:98:79: error: request for member 'second' in 'i', which is of non-class type 'int'
   if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
                                                                               ^
dragon2.cpp: In function 'void proc_sweep(int)':
dragon2.cpp:125:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : s1[gnum]){
      ^
dragon2.cpp:125:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : s1[gnum]){
            ^
dragon2.cpp:125:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : s1[gnum]){
                ^
dragon2.cpp:126:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
           ^
dragon2.cpp:126:57: error: request for member 'pos' in 'i', which is of non-class type 'int'
   while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
                                                         ^
dragon2.cpp:129:9: error: request for member 'idx' in 'i', which is of non-class type 'int'
   ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
         ^
dragon2.cpp:129:19: error: request for member 'dx' in 'i', which is of non-class type 'int'
   ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
                   ^
dragon2.cpp:129:37: error: request for member 'e' in 'i', which is of non-class type 'int'
   ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
                                     ^
dragon2.cpp:129:54: error: request for member 's' in 'i', which is of non-class type 'int'
   ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
                                                      ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:157:8: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
    for(auto &j : grp[x]){
        ^
dragon2.cpp:157:14: error: ISO C++ forbids declaration of 'j' with no type [-fpermissive]
    for(auto &j : grp[x]){
              ^
dragon2.cpp:157:18: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
    for(auto &j : grp[x]){
                  ^
dragon2.cpp:158:24: error: request for member 'first' in 'j', which is of non-class type 'int'
     add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
                        ^
dragon2.cpp:158:42: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
                                          ^
dragon2.cpp:158:57: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
                                                         ^
dragon2.cpp:159:21: error: request for member 'first' in 'j', which is of non-class type 'int'
     add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
                     ^
dragon2.cpp:159:40: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
                                        ^
dragon2.cpp:159:55: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
                                                       ^
dragon2.cpp:163:8: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
    for(auto &j : grp[y]){
        ^
dragon2.cpp:163:14: error: ISO C++ forbids declaration of 'j' with no type [-fpermissive]
    for(auto &j : grp[y]){
              ^
dragon2.cpp:163:18: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
    for(auto &j : grp[y]){
                  ^
dragon2.cpp:164:18: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep2(j.second, x, i);
                  ^
dragon2.cpp:165:18: error: request for member 'first' in 'j', which is of non-class type 'int'
     add_sweep3(j.first, j.second, x, i);
                  ^
dragon2.cpp:165:27: error: request for member 'second' in 'j', which is of non-class type 'int'
     add_sweep3(j.first, j.second, x, i);
                           ^
dragon2.cpp:137:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
dragon2.cpp:139:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
                                            ^
dragon2.cpp:141:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
                                          ^
dragon2.cpp:148:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
dragon2.cpp:151:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^